字符串匹配[作业部落]
单纯判断模式串是否在文本串中出现：
#define rg register #define _ 1000001 using namespace std; int n,num,team[_<<1],result; char aa[_]; struct AC_aotomatic { int fail,son[26],end,it;//end:有多少个字符串在此点结束 }trie[_]; inline int read() { rg int save=0,w=1;rg char q=getchar(); while(q<'0'||q>'9'){if(q=='-')w=-1;q=getchar();} while(q>='0'&&q<='9')save=(save<<3)+(save<<1)+q-'0',q=getchar(); return save*w; } inline void insert(rg int &fa,rg char q) { if(!trie[fa].son[q-'a'])trie[fa].son[q-'a']=++num; fa=trie[fa].son[q-'a']; trie[fa].it=q-'a'; } inline void get_fail() { rg int i,j; rg int head=0,tail=0; for(i=0;i<26;++i) { if(trie[0].son[i]) team[++tail]=trie[0].son[i], trie[trie[0].son[i]].fail=0; //第一层的fail必须指向root(即0)!!! //假如到第一层就匹配失败了,自然要从第一层重新找一个点匹配 } do { head++; rg int u=team[head]; for(i=0;i<26;++i) { if(trie[u].son[i]) { trie[trie[u].son[i]].fail=trie[trie[u].fail].son[i]; //和KMP相像的是,son[i]的fail指向的是 前面已有后缀与son[i]的前一部分相同,而自己等于son[i]的点,也就可以待匹配 team[++tail]=trie[u].son[i]; } else trie[u].son[i]=trie[trie[u].fail].son[i]; //当前节点的这个子节点指向 当前节点的fail指针指向的点 的这个子节点 } }while(head<tail); } inline void doit() { rg int i,j=0; rg int l=strlen(aa); // cout<<aa<<endl; for(i=0;i<l;++i) { j=trie[j].son[aa[i]-'a'];//跳儿子,若son[aa[i]-'a']为空,就指回根了 for(rg int t=j; t&&trie[t].end!=-1 ;t=trie[t].fail)//跳fail指针 { result+=trie[t].end; trie[t].end=-1; //因为这个循环前面一行有个跳儿子的操作,所以如果跳儿子跳到根了,可能会把fail指针已经跳到过的字符串再跳一遍,所以在此加一个便于判定走过的操作 } } printf("%d\n",result); } int main() { n=read(); rg int i,j; for(i=1;i<=n;++i) { rg char q=getchar();rg int fa=0; while(q<'a'||q>'z')q=getchar(); while(q>='a'&&q<='z')insert(fa,q),q=getchar(); trie[fa].end++; // cout<<fa<<' '<<trie[fa].end<<endl; } rg char q=getchar();j=-1; while(q<'a'||q>'z')q=getchar(); while(q>='a'&&q<='z')aa[++j]=q,q=getchar(); get_fail(); doit(); return 0; }
计算模式串出现次数：
#define rg register #define _ 10000005 #define max(x,y) x<y?y:x using namespace std; int n,ans[1000],to[11],team[_],maxx,num,record[1000],num_of_edges; char aa[_],ss[11][51]; struct pp { int next,to; }edge[_<<1]; struct AC_Automatic { int fail,son[27],end; }trie[1000]; inline int read() { rg int save=0,w=1;rg char q=getchar(); while(q<'0'||q>'9'){if(q=='-')w=-1;q=getchar();} while(q>='0'&&q<='9')save=(save<<3)+(save<<1)+q-'0',q=getchar(); return save*w; } inline void insert(rg int &i,rg char q) { if(!trie[i].son[q-'a'])trie[i].son[q-'a']=++num; i=trie[i].son[q-'a']; } inline void get_fail() { rg int head=0,tail=0,i; for(i=0;i<26;++i) { if(trie[0].son[i]) trie[trie[0].son[i]].fail=0,team[++tail]=trie[0].son[i]; } do { head++; rg int u=team[head]; for(i=0;i<26;++i) { if(trie[u].son[i]) { team[++tail]=trie[u].son[i]; trie[trie[u].son[i]].fail=trie[trie[u].fail].son[i]; } else trie[u].son[i]=trie[trie[u].fail].son[i]; } }while(head<tail); } inline void doit() { rg int i,j=0; rg int l=strlen(aa); for(i=0;i<l;++i) { j=trie[j].son[aa[i]-'a']; ans[j]++; } } inline void add(rg int from,rg int to) { edge[++num_of_edges]=(pp){record[from],to}; record[from]=num_of_edges; } void dfs(rg int i) { for(rg int j=record[i];j;j=edge[j].next) { rg int to=edge[j].to; dfs(to); ans[i]+=ans[to]; } } inline void solve() { rg int i,j; for(i=1;i<=num;++i) add(trie[i].fail,i); dfs(0); } int main() { n=read(); // cout<<"________"<<n<<"\n"; rg int i,j; for(i=1;i<=n;++i) { rg char q=getchar();rg int fa=0,j=-1; while(q<'a'||q>'z')q=getchar(); while(q>='a'&&q<='z')ss[i][++j]=q,insert(fa,q),q=getchar(); // cout<<ss[i]<<endl; trie[fa].end++; to[i]=fa; } rg char q=getchar();j=-1; while(q<'a'||q>'z')q=getchar(); while(q>='a'&&q<='z')aa[++j]=q,q=getchar(); // cout<<aa<<endl; get_fail(); doit(); solve(); for(i=1;i<=n;++i) printf("%s %d\n",ss[i],ans[to[i]]); return 0; }