AC自动机自学笔记
目录用途：
要学习之前肯定是要知道ac自动机是拿来干嘛的噻。
- 可以在一个字符串S中找到s1,s2,s3....的出现点以及出现次数。
定义：
AC，当然不是accepeted啦，而是某个名人（懒得记）研究出来的算法。
AC自动机作为一个机器需要两个东西支持，思想上叫做Kmp，行动上叫做tire
Tire字典树
这tire是处理多个模式串的基础
没学过？那你看什么ac自动机，回去巩固基础！
学过？那就不再赘述了。
Kmp算法：
同上，不再赘述
ac自动机
ac自动机其实相比于kmp而言就是在tire树上做cmp。
首先我们弄懂fail是什么意思，假如说我当前匹配到了bcd，但是d失配了，我可以通过fail建立一条边找到一个后缀为d的最长的东西来继续尝试匹配。
直到匹配成功或者只剩下这一个字母。特别地，只剩下一个时，他的fail边建向树根。
由于是在树上建立fail，我们找到一个节点时必须要知道其父节点是否出现过自己这个字符，所以要使用bfs来搞。
代码（基础版）：
#include<bits/stdc++.h>
using namespace std;
int tree[3000005][30];
int val[3000005];
int fail[3000005];
int cnt=0;
void add(string s){
int sz=s.size();
int p=0;
for(int i=0;i<sz;i++){
int c=s[i]-'a';
if(!tree[p][c]){
tree[p][c]=++cnt;
}
p=tree[p][c];
}
val[p]++;
}
void build(){
queue<int>q;
for(int i=0;i<26;i++){
if(tree[0][i]){
q.push(tree[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tree[u][i]){
fail[tree[u][i]]=tree[fail[u]][i];
q.push(tree[u][i]);
}
else{
tree[u][i]=tree[fail[u]][i];
}
}
}
}
int query(string s){
int u=0;
int ret=0;
for(int i=0;i<s.size();i++){
u=tree[u][s[i]-'a'];
for(int j=u;j&&val[j]!=-1;j=fail[j]){
ret+=val[j];
val[j]=-1;
}
}
return ret;
}
int main(){
int n;
cin >>n;
for(int i=1;i<=n;i++){
string s;
cin >>s;
add(s);
}
build();
string s;
cin >>s;
cout<<query(s);
}
代码记忆方式：
build有儿子ftui=tfui，没儿子tui=tfui。
加强版分析：
其实大体思路是一样的，不一样的是每一次跳fail的时候看看是不是跳到了一个叶子节点（也不一定就是，总之在建tire时标记一下），如果是，说明存在一个模版串，在相应位置val++
最后把所有val找最大值，然后每个地方记录一下父亲，往回跳就好了，时间复杂度不会太高，怕的话可以看看以后更新的对于ac自动机的优化
代码（加强版）
#include<bits/stdc++.h>
using namespace std;
int tree[3000005][30];
int fail[3000005];
int val[300005];
bool tail[300005];
int fa[300005];
char rev[300005];
int cnt;
void clear(){
for(int i=0;i<=cnt;i++){
for(int j=0;j<26;j++){
tree[i][j]=0;
}
fail[i]=0;
val[i]=0;
tail[i]=0;
fa[i]=0;
}
cnt=0;
}
void add(string s){
int sz=s.size();
int p=0;
for(int i=0;i<sz;i++){
int c=s[i]-'a';
if(!tree[p][c]){
tree[p][c]=++cnt;
rev[cnt]=s[i];
fa[cnt]=p;
}
p=tree[p][c];
}
tail[p]=1;
}
void build(){
queue<int>q;
for(int i=0;i<26;i++){
if(tree[0][i]){
q.push(tree[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tree[u][i]){
fail[tree[u][i]]=tree[fail[u]][i];
q.push(tree[u][i]);
}
else{
tree[u][i]=tree[fail[u]][i];
}
}
}
}
void query(string s){
int sz=s.size();
int u=0;
int ret=0;
for(int i=0;i<sz;i++){
u=tree[u][s[i]-'a'];
for(int j=u;j;j=fail[j]){
if(tail[j]==1){
val[j]++;
}
}
}
}
void print(int pos){
stack<char>q;
while(pos){
q.push(rev[pos]);
pos=fa[pos];
}
while(q.size()){
cout<<q.top();
q.pop();
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
int n;
while(cin >> n){
if(n==0){
return 0;
}
clear();
for(int i=1;i<=n;i++ ){
string s;
cin >> s;
add(s);
}
build();
string s;
cin >>s;
query(s);
int mx=0;
for(int i=0;i<=cnt;i++){
mx=max(mx,val[i]);
}
cout<<mx<<endl;
for(int i=0;i<=cnt;i++){
if(val[i]==mx){
print(i);
}
}
}
}