C++常用算法模板.docx

《C++常用算法模板.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、KMP算法#include#include#defineN20000charst1[N],st2[N],pre[N];intans,len1,len2;voidkmp1(){inti,j=0;for(i=2;i<=len1;i++){while(j&&st1[j+1]!=st1[i])j=pre[j];if(st1[j+1]==st1[i])j++;pre[i]=j;}}voidkmp2(){inti,j=0;for(i=1;i<=len2;i++){while(j&&st1[j+1]!=st2[i])j=pre[j];if(st1[j

2、+1]==st2[i])j++;if(j==len1)ans++,j=pre[j];}}intmain(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%s",st1+1);len1=strlen(st1+1);scanf("%s",st2+1);len2=strlen(st2+1);kmp1();kmp2();printf("%d",ans);return0;}trie#include#include#defineN1000usingnamespaces

3、td;intn,i,len,ok,tot,trie[N][30];intflag[N];chars[100];voidaddtrie(intlen){intx,i,ch;x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}if(flag[x]==1)ok=1;elseok=0;flag[x]=1;}intmain(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n

4、);tot=1;for(i=1;i<=n;i++){scanf("%s",s+1);len=strlen(s+1);addtrie(len);if(ok)printf("YES");elseprintf("NO");}return0;}karp-rabin#include#include#defineM#defineN#definemo10000intn,m,i,key[N],ha,w,len,ss,ans;chars[10000];intlast[N],other[M],next[M];intjianyan(intx,inty

5、){for(inti=0;i

6、anf("%s",s+1);len=strlen(s+1);for(i=1;i<=len;i++)key[i]=(key[i-1]*m+s[i])%mo;ss=1;for(i=1;i<=n;i++)ss=ss*m%mo;for(i=n;i<=len;i++){ha=((key[i]-key[i-n]*ss)%mo+mo)%mo;if(inhash(ha,i-n+1))ans++;}printf("%d",ans);return0;}AC自动机#include#include#includeusingnamespaces

7、td;#defineNinttest,n,tot,ans,i;intjs[N],flag[N],g[N];inttrie[N][26];chars[];voidaddtrie(intlen){inti,ch,x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}js[x]++;}voidbfs(){intx,i,j,y;queueq;q.push(1);while(q.size()){x=q.front();q