#include<bits/stdc++.h> usingnamespace std; constint maxn=1e6+10; structnote{ int son[26];//26个英文字母 int flag;//标记是否是末端 int fail;//fail指针 }trie[maxn]; int n,cnt; string s; queue<int>q;
voidinsert(string s)//构建trie { int u=1; for(int i=0;i<s.length();++i) { int v=s[i]-'a'; if(!trie[u].son[v]) trie[u].son[v]=++cnt; u=trie[u].son[v]; } trie[u].flag++; }
voidgetFail() { for(int i=0;i<26;++i) trie[0].son[i]=1;//初始化0的所有儿子都是0 q.push(1);//将根节点压入队列 trie[1].fail=0;//1为root,将1的fail指向0 while(!q.empty())//bfs { int u=q.front(); q.pop(); for(int i=0;i<26;++i) { int v=trie[u].son[i];//其子节点 int Fail=trie[u].fail; if(!v)//表示不存在该节点 { trie[u].son[i]=trie[Fail].son[i]; continue; } trie[v].fail=trie[Fail].son[i]; q.push(v);//存在实节点就压入队列 } } }
intquery(string s) { int u=1,ans=0; for(int i=0;i<s.length();++i) { int v=s[i]-'a'; int k=trie[u].son[v]; while(k>1&&trie[k].flag!=-1) { ans+=trie[k].flag; trie[k].flag=-1;//标记已经找过了 k=trie[k].fail; } u=trie[u].son[v];//到下一个儿子 } return ans; }