2020-2021:teams:hotpot:ac自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:ac自动机 [2020/08/21 16:57] lotk |
2020-2021:teams:hotpot:ac自动机 [2020/08/26 15:44] (当前版本) lotk |
||
|---|---|---|---|
| 行 31: | 行 31: | ||
| {{:2020-2021:teams:hotpot:ac2.png?400|}} | {{:2020-2021:teams:hotpot:ac2.png?400|}} | ||
| + | 为了解决此类问题，我们又可以引入后缀链接，$nxt(i)$ 表示从$i$沿着失配边转移，能够到达的第一个单词结点。 | ||
| + | |||
| + | 后缀链接可以在失配指针之后求出，如果 $fail(i)$ 为单词结点，则 $nxt(i)=fail(i)$,否则 $nxt(i)=nxt(fail(i))$ | ||
| + | |||
| + | ====优化==== | ||
| + | |||
| + | 由于每次失配时需要用到失配指针，每次加入字符时经过节点数不确定，复杂度可能退化，但对于一个状态，添加一个字符后，转移到的状态是确定的，这也意味着我们可以预处理每一个状态可能装一道的所有状态。 | ||
| + | |||
| + | 对于节点 $i$ ,如果它有字符 $c$的出边,则加入 $c$ 时，它可以直接转移到该边指向结点，否则应该转移到fail(i)加入对应字符转移到的点上，我们可以用递推的方式求出这些转移方式，加入这些边，得到$Trie$图 | ||
| + | |||
| + | ====模板题==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P3808|P3808 【模板】AC自动机（简单版）]] | ||
| + | |||
| + | ps:本题由于只记录串出现次数，可以通过标记来优化复杂度。 | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<iostream> | ||
| + | #include<iomanip> | ||
| + | #include<cstdio> | ||
| + | #include<algorithm> | ||
| + | #include<map> | ||
| + | #include<stack> | ||
| + | #include<queue> | ||
| + | #include<complex> | ||
| + | #include<cmath> | ||
| + | #include<cstring> | ||
| + | using namespace std; | ||
| + | const int maxn=1000005; | ||
| + | char s[maxn]; | ||
| + | int cnt,ch[maxn][26],Count[maxn],fail[maxn]; | ||
| + | int nxt[maxn]; | ||
| + | void Insert(){ | ||
| + | scanf("%s",s+1); | ||
| + | int len=strlen(s+1); | ||
| + | int rt=0; | ||
| + | for(int i=1;i<=len;++i){ | ||
| + | int t=s[i]-'a'; | ||
| + | if(!ch[rt][t])ch[rt][t]=++cnt; | ||
| + | rt=ch[rt][t]; | ||
| + | } | ||
| + | ++Count[rt]; | ||
| + | } | ||
| + | queue<int> Q; | ||
| + | void Build_AC(){ | ||
| + | Q.push(0); | ||
| + | while(!Q.empty()){ | ||
| + | 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(Count[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]; | ||
| + | } | ||
| + | } | ||
| + | void Query(){ | ||
| + | scanf("%s",s+1); | ||
| + | int len=strlen(s+1),rt=0; | ||
| + | int ans=0; | ||
| + | for(int i=1;i<=len;++i){ | ||
| + | int t=s[i]-'a'; | ||
| + | int a=ch[rt][t]; | ||
| + | while(a){ | ||
| + | if(Count[a]==-1)break; | ||
| + | ans+=Count[a]; | ||
| + | Count[a]=-1; | ||
| + | a=nxt[a]; | ||
| + | } | ||
| + | rt=ch[rt][t]; | ||
| + | } | ||
| + | printf("%d",ans); | ||
| + | } | ||
| + | int n; | ||
| + | int main(){ | ||
| + | scanf("%d",&n); | ||
| + | for(int i=1;i<=n;++i)Insert(); | ||
| + | Build_AC(); | ||
| + | Query(); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P3796|P3796 【模板】AC自动机（加强版）]] | ||
| + | |||
| + | ps:本题按输入顺序输出所有出现次数最多的模式串。保留所有的串编号最后排序输出即可。 | ||
| + | |||
| + | <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=75*155; | ||
| + | char s[1000005]; | ||
| + | bool str[maxn]; | ||
| + | int ch[maxn][26],cnt,fail[maxn]; | ||
| + | int prt[maxn],nxt[maxn]; | ||
| + | int uni[maxn]; | ||
| + | char alp[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; | ||
| + | prt[cnt]=x;alp[cnt]=s[i]; | ||
| + | } | ||
| + | x=ch[x][t]; | ||
| + | } | ||
| + | str[x]=true;uni[x]=bh; | ||
| + | } | ||
| + | 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]; | ||
| + | } | ||
| + | } | ||
| + | typedef pair<int,int> pr; | ||
| + | vector<pr> ans; | ||
| + | int MAX,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]; | ||
| + | if(num[nw]==MAX)ans.push_back(pr(uni[nw],nw)); | ||
| + | if(num[nw]>MAX){ | ||
| + | MAX=num[nw];ans.clear(); | ||
| + | ans.push_back(pr(uni[nw],nw)); | ||
| + | } | ||
| + | nw=nxt[nw]; | ||
| + | } | ||
| + | x=ch[x][t]; | ||
| + | } | ||
| + | } | ||
| + | void write(int x){ | ||
| + | if(!x)return; | ||
| + | write(prt[x]); | ||
| + | printf("%c",alp[x]); | ||
| + | } | ||
| + | void Print(){ | ||
| + | printf("%d\n",MAX); | ||
| + | sort(ans.begin(),ans.end()); | ||
| + | for(auto x:ans){ | ||
| + | write(x.second); | ||
| + | puts(""); | ||
| + | } | ||
| + | } | ||
| + | void clear(){ | ||
| + | MAX=cnt=0; | ||
| + | memset(str,0,sizeof str); | ||
| + | memset(ch,0,sizeof ch); | ||
| + | memset(fail,0,sizeof fail); | ||
| + | memset(nxt,0,sizeof nxt); | ||
| + | memset(num,0,sizeof num); | ||
| + | memset(prt,0,sizeof prt); | ||
| + | ans.clear(); | ||
| + | } | ||
| + | int main(){ | ||
| + | while(true){ | ||
| + | clear(); | ||
| + | n=read(); | ||
| + | if(!n)break; | ||
| + | for(int i=1;i<=n;++i)Insert(i); | ||
| + | build_ac(); | ||
| + | //cout<<'a'<<endl; | ||
| + | qans(); | ||
| + | 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; | ||
| + | } | ||
| + | |||
| + | </code> | ||
2020-2021/teams/hotpot/ac自动机.1598000271.txt.gz · 最后更改: 2020/08/21 16:57 由 lotk
