某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
fail树的棵题。
朴素想法就是建立AC自动机，每个串都匹配一遍，这样显然TLE。
但是实际上我们就是相当于查询一个单词x在另一个单词y内出现了多少次。
对于上面这个问题，一种朴素想法是AC自动机，把y单词的所有结点的fail都跑一遍，看看有没有指向x末尾的，有答案++。
其实我们只用到了fail指针，所以不如我们把fail提出来重新建树，减少状态。
令cnt[i]为0~i的路径拼起来字符串出现次数。
这样我们建立了fail树，从下往上累加cnt即可，最终答案就是查询单词的末尾记录的cnt。
我们因为只进行了一次dfs，比之前查询n次的效率显然高到不知道哪里去了。
#include#include #include #include #include #include #include #include using namespace std;typedef long long ll;const int N=220;const int S=1e6+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct trie{ int a[26],fail;}tr[S];struct node{ int to,nxt;}e[S];int m,tot,cnt[S],ed[N],sum,head[S];char s[S];queue q;inline void add(int u,int v){ e[++sum].to=v;e[sum].nxt=head[u];head[u]=sum;}void insert(int id){ int len=strlen(s),now=0; for(int i=0;i
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客： +
+++++++++++++++++++++++++++++++++++++++++++