ac自动机

又一次意识到自己是多么的菜：）

ac自动机

就是在trie树上连fail指针

fail指针的作用和kmp的next数组一样的

[POI2000]病毒

ac自动机入坑题

在trie图已经建好的情况下

我们把给定病毒串的末尾和fail指针连向其末尾的点都叫做危险节点

如果能不经过危险节点在trie图上找到一个环

那就按这个环一直循环下去就找到了长度无限的串

归纳：

看到“循环”“无限长度”联想到图论的环路

对失配指针的熟练掌握

另：dfs中找环路用的vis回来要刷零剪枝用的vis不刷零

 1 int main(){
 2     scanf("%d", &n);
 3     for(int i = 1; i <= n; i++){
 4         char p[N];
 5         scanf("%s", p);
 6         ins(p);
 7     }
 8     build();
 9     dfs(0);
10     printf("NIE");
11     return 0;
12 }

框架

 1 void build(){
 2     queue<int> q;
 3     if(ac[0].c[1]) q.push(ac[0].c[1]);
 4     if(ac[0].c[0]) q.push(ac[0].c[0]);
 5     while(!q.empty()){
 6         int fro = q.front(); q.pop();
 7         ac[fro].e |= ac[ac[fro].fail].e;
 8         for(int i = 0; i <= 1; i++){
 9             if(ac[fro].c[i]){
10                 ac[ac[fro].c[i]].fail = ac[ac[fro].fail].c[i];
11                 q.push(ac[fro].c[i]);
12             }
13             else ac[fro].c[i] = ac[ac[fro].fail].c[i];
14         }
15     }
16 }

build

 1 void dfs(int x){
 2     if(vis[x]){
 3         printf("TAK");
 4         exit(0);
 5     }
 6     if(stop[x] || ac[x].e) return ;
 7     vis[x] = stop[x] = 1;
 8     dfs(ac[x].c[0]);
 9     dfs(ac[x].c[1]);
10     vis[x] = 0;
11 }

dfs