输入一些子串 输入母串，看母串中有多少个子串。(并没有统计每个出现了多少次，只是看哪些出现过，所以那个count1标记为-1)//出现过一次就不再遍历了
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> using namespace std; const int maxn = 1000000+10; const int n = 26; char y[maxn]; int result=0; struct Trie { Trie *next[n]; int count1; Trie *fail; Trie() { fail=NULL; count1=0; for(int i=0;i<n;i++) next[i]=NULL; } }; Trie *root; void buildTrie(char *str) { int len=strlen(str); Trie *p=root,*q; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]==NULL) p->next[id]=new Trie(); p=p->next[id]; } p->count1++; } void buildfail() { queue<Trie* > q; q.push(root); while(!q.empty()) { Trie *p=q.front();q.pop(); for(int i=0;i<n;i++) { if(p->next[i]!=NULL) { if(p==root) p->next[i]->fail=root; else{ Trie *temp=p->fail; while(temp!=NULL){ if(temp->next[i]!=NULL){ p->next[i]->fail=temp->next[i]; break; } if(temp->next[i]==NULL) temp=temp->fail; } if(temp==NULL) p->next[i]->fail=root; } q.push(p->next[i]); } } } } int query(char *str) { int len = strlen(str); Trie *p=root; for(int i=0;i<len;i++) { int id=str[i]-'a'; while(p->next[id]==NULL&&p!=root) p=p->fail; p=p->next[id]; if(p==NULL) p=root; Trie *temp=p; while(temp!=root&&temp->count1!=-1)//扫后缀 { result+=temp->count1; temp->count1=-1; temp=temp->fail; } } return result; } int main() { int case1; scanf("%d",&case1); while(case1--) { result=0; int n; head=0,tail=0; scanf("%d",&n); root=new Trie(); while(n--) { char s[60]; scanf("%s",s); buildTrie(s); } buildfail(); scanf("%s",y); printf("%d\n",query(y)); } return 0; }如果统计在母串中出现了多少次子串的话。我们在query中是对后缀的统计。所以把那个-1去掉就好了。
数组版，统计母串中出现了多少次子串
#include <iostream> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) const int maxn = 5e5+10; const int sz=4; struct Trie { int next[maxn][30],fail[maxn],ed[maxn]; int root,L; int newnode() { for(int i=0;i<26;i++) next[L][i]=-1; ed[L++]=0; return L-1; } void init() { L=0; root=newnode(); } void sert(char buf[]) { int len=strlen(buf); int now=root; for(int i=0;i<len;i++) { if(next[now][buf[i]-'a']==-1) next[now][buf[i]-'a']=newnode(); now=next[now][buf[i]-'a']; } ed[now]++; } void buildfail() { queue<int> Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i] == -1) next[root][i]=root;//这里为什么要改变next？为了之后query的时候 else { fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()) { int now=Q.front(); Q.pop(); for(int i=0;i<26;i++) if(next[now][i] == -1) next[now][i] = next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int query(char *str) { int len=strlen(str); int now=root; int res=0; for(int i=0;i<len;i++) { int id=str[i]-'a',temp; now=next[now][id],temp=now; while(temp!=root) { res+=ed[temp]; ed[temp]=0; temp=fail[temp]; } } return res; } }; char s1[1000010]; Trie ac; int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); ac.init(); for(int i=0;i<n;i++) { scanf("%s",s1); ac.sert(s1); } ac.buildfail(); scanf("%s",s1); printf("%d\n",ac.query(s1)); } return 0; }数组版感觉写起来真舒服，板子来自kb神
