题解 P3808 【【模板】AC自动机（简单版）】

蒟蒻终于把~~WA~~ AC自动机打出来了。。。 ## AC自动机讲解 AC自动机简单来说就是Tire Tree + ~~看毛片~~KMP，也就是~~在~~树上~~看毛片~~KMP。 AC自动机用来解决多模式串匹配，也就是给好几个子串，一个很长很长很长很长很长的母串，让你处理一些问题，比如什么子串出现的次数之类的。 怎么做咧？ 你先把所有的子串丢到Trie上，比如四个字符串:abcd，abd，bcd，cd，建立如下图Trie树：  然后我们就要树上看毛片了！ 和KMP中的next数组很像，我们定义fail数组，fail[i]为与以i节点为结尾的串的后缀有最大公共长度的前缀的结尾编号。这句话是不是有点绕orz。 我们来分析一下什么意思：对于以d结尾的子串abcd，不存在任何一个其他子串的前缀与abcd匹配，但bcd与abcd的后缀bcd匹配，这是匹配到的最长情况，于是这个d上的fail指针就指向bcd上的d。然后，如果没有找到任何一个前缀与当前串的任何一个后缀一样的话，那么fail只能指到根了。和KMP的原理一样，fail跳到的地方必然这个子串的前面不用再比较了，因为根据fail的定义，它的已经前缀已经被比较过并且匹配了。只用再往后比就行了。放一下图：  记num[i]为以i节点为结尾的子串有几个,我们对于每个子串，都在这个子串的结尾，把num++,以方便以后跳来跳去的时候统计。匹配到当前节点，就加上当前节点的num，当然，加过了就不要再加了，因为这道题并不是统计所有子串出现的总数，而是有多少子串出现了。 那么。。对于匹配的时候，当前节点配不下去了怎么办？比如我们尝试匹配abcde，abcd都顺利匹配了，这时候我们发现d并没有e这个节点，那么我们就跳到d的fail指针，也就是bcd上的d，还是没有e，那么继续，到cd上的d，还是没有，只能到根了，还是没有。。。那么。。。就没有了。我们处理的时候，就可以把abcd上的d的不存在的儿子，指向d的fail指针的这个儿子，好像还是有点绕。。 那么继续上图，（这里的e点都为虚线，实际上是没有的）：  也就是说，我们在不断尝试，有没有其他前缀后面跟着e的。这样处理之后，就简单方便多了。 ------------ ## 代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,cnt=0; char tmp[1000100]; struct node { int fail,num; int ch[30]; }tr[1000100]; int q[1000100]; void build()//建立Trie树 { int len=strlen(tmp),u=0; for(int i=0;i<len;i++) { int s=tmp[i]-'a'; if(tr[u].ch[s]==0) tr[u].ch[s]=++cnt; u=tr[u].ch[s]; } tr[u].num++; } void get_fail() { int l=0,r=0; for(int i=0;i<26;i++) if(tr[0].ch[i]!=0) { tr[tr[0].ch[i]].fail=0; q[++r]=tr[0].ch[i]; } while(l<r) { int u=q[++l]; for(int i=0;i<26;i++) { int v=tr[u].ch[i]; if(v) { tr[v].fail=tr[tr[u].fail].ch[i];//处理fail指针，是它父亲的fail指针的i儿子 q[++r]=v; } else tr[u].ch[i]=tr[tr[u].fail].ch[i];//处理所说的“虚指针”，WA了好几次因为把这里的tr[u].ch[i]也替换成v了。。 } } } int AC() { int len=strlen(tmp); int u=0,ans=0; for(int i=0;i<len;i++) { int s=tmp[i]-'a'; u=tr[u].ch[s]; int v=u; while(v && tr[v].num!=-1) { ans+=tr[v].num; tr[v].num=-1;//加过了之后就不用再加了 v=tr[v].fail; } } return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",tmp); build(); } tr[0].fail=0; get_fail(); scanf("%s",tmp); printf("%d",AC()); return 0; } ``` 你会发现代码和yyb大佬的很像，因为我是看了yyb的题解才打出来的。。yyb的很清楚，所以我放上来只是凑个长度的没错