2020-2021:teams:hotpot:ac自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:ac自动机 [2020/08/26 15:29] lotk |
2020-2021:teams:hotpot:ac自动机 [2020/08/26 15:44] (当前版本) lotk |
||
|---|---|---|---|
| 行 236: | 行 236: | ||
| Print(); | Print(); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P5357|P5357 【模板】AC自动机（二次加强版）]] | ||
| + | |||
| + | ps:本题方法基本同上，记录一下每个串在trie上对应的点就可以了。 | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<algorithm> | ||
| + | #include<stack> | ||
| + | #include<ctime> | ||
| + | #include<cstring> | ||
| + | #include<cmath> | ||
| + | #include<iostream> | ||
| + | #include<iomanip> | ||
| + | #include<cstdio> | ||
| + | #include<queue> | ||
| + | using namespace std; | ||
| + | inline int read(){ | ||
| + | int num=0,f=1;char x=getchar(); | ||
| + | while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();} | ||
| + | while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();} | ||
| + | return num*f; | ||
| + | } | ||
| + | const int maxn=200005; | ||
| + | char s[maxn*10]; | ||
| + | bool str[maxn]; | ||
| + | int ch[maxn][26],cnt,fail[maxn]; | ||
| + | int nxt[maxn],uni[maxn]; | ||
| + | int n; | ||
| + | void Insert(int bh){ | ||
| + | scanf("%s",s); | ||
| + | int len=strlen(s); | ||
| + | int x=0; | ||
| + | for(int i=0;i<len;++i){ | ||
| + | int t=s[i]-'a'; | ||
| + | if(!ch[x][t])ch[x][t]=++cnt; | ||
| + | x=ch[x][t]; | ||
| + | } | ||
| + | str[x]=true;uni[bh]=x; | ||
| + | } | ||
| + | queue<int> Q; | ||
| + | void build_ac(){ | ||
| + | Q.push(0); | ||
| + | while(Q.size()){ | ||
| + | int x=Q.front();Q.pop(); | ||
| + | for(int i=0;i<26;++i) | ||
| + | if(ch[x][i]){ | ||
| + | if(x){ | ||
| + | fail[ch[x][i]]=ch[fail[x]][i]; | ||
| + | if(str[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i]; | ||
| + | else nxt[ch[x][i]]=nxt[ch[fail[x]][i]]; | ||
| + | } | ||
| + | Q.push(ch[x][i]); | ||
| + | }else ch[x][i]=ch[fail[x]][i]; | ||
| + | } | ||
| + | } | ||
| + | int num[maxn]; | ||
| + | void qans(){ | ||
| + | scanf("%s",s); | ||
| + | int len=strlen(s); | ||
| + | int x=0; | ||
| + | for(int i=0;i<len;++i){ | ||
| + | int t=s[i]-'a'; | ||
| + | int nw=ch[x][t]; | ||
| + | while(nw){ | ||
| + | if(str[nw])++num[nw]; | ||
| + | nw=nxt[nw]; | ||
| + | } | ||
| + | x=ch[x][t]; | ||
| + | } | ||
| + | } | ||
| + | int main(){ | ||
| + | n=read(); | ||
| + | for(int i=1;i<=n;++i)Insert(i); | ||
| + | build_ac(); | ||
| + | qans(); | ||
| + | for(int i=1;i<=n;++i)printf("%d\n",num[uni[i]]); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
2020-2021/teams/hotpot/ac自动机.1598426967.txt.gz · 最后更改: 2020/08/26 15:29 由 lotk
