应用场景
多模式匹配问题
多串匹配一个串
预定义
1 const int N = 1e6+100; 2 char s[N],m[N]; 3 struct node 4 { 5 int son[26]; 6 int fail; 7 int count; 8 }ac[N]; 9 int tot = 0;
初始化
1 // 涉及多组时需要用到 2 void init() 3 { 4 for(int i = 0;i < N;i++) 5 { 6 memset(ac[i].son,0,sizeof ac[i].son); 7 ac[i].count = 0; 8 ac[i].fail = 0; 9 } 10 }
插入单词
1 void Insert(char *s) 2 { 3 int len = strlen(s); 4 int now = 0; 5 int tmp; 6 for(int i = 0;i < len;i++) 7 { 8 tmp = s[i]-'a'; 9 if(ac[now].son[tmp] == 0) 10 ac[now].son[tmp] = ++tot; 11 now = ac[now].son[tmp]; 12 } 13 ac[now].count++; 14 }
构造fail指针
1 void MakeFail() 2 { 3 queue<int> q; 4 for(int i = 0;i < 26;i++) 5 { 6 if(ac[0].son[i] != 0) 7 { 8 ac[ac[0].son[i]].fail = 0; 9 q.push(ac[0].son[i]); 10 } 11 } 12 while(!q.empty()) 13 { 14 int u = q.front(); 15 q.pop(); 16 for(int i = 0;i < 26;i++) 17 { 18 if(ac[u].son[i] != 0) 19 { 20 ac[ac[u].son[i]].fail = ac[ac[u].fail].son[i]; 21 q.push(ac[u].son[i]); 22 } 23 else 24 ac[u].son[i] = ac[ac[u].fail].son[i]; 25 } 26 } 27 }
AC自动机匹配
1 int Query(char *s) 2 { 3 int len = strlen(s); 4 int now = 0,ans = 0,tmp; 5 for(int i = 0;i < len;i++) 6 { 7 tmp = s[i]-'a'; 8 now = ac[now].son[tmp]; 9 for(int t = now;t && ac[t].count != -1;t = ac[t].fail) 10 { 11 ans += ac[t].count; 12 ac[t].count = -1; 13 } 14 } 15 return ans; 16 }
主函数
1 int main() 2 { 3 int t; 4 scanf("%d",&t); 5 while(t--) 6 { 7 scanf("%s",s); 8 Insert(s); 9 } 10 ac[0].fail = 0; // 切记 11 MakeFail(); 12 scanf("%s",m); 13 printf("%d ",Query(m)); 14 return 0; 15 }