搜索
KMP算法#includecstdio#includecstring#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+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\n,ans);return0;}trie#includecstdio#includecstring#defineN1000usingnamespacestd;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);tot=1;for(i=1;i=n;i++){scanf(%s,s+1);len=strlen(s+1);addtrie(len);if(ok)printf(YES\n);elseprintf(NO\n);}return0;}karp-rabin#includecstdio#includecstring#defineM1000000#defineN100000#definemo10000intn,m,i,key[N],ha,w,len,ss,ans;chars[10000];intlast[N],other[M],next[M];intjianyan(intx,inty){for(inti=0;in;i++)if(s[x+i]!=s[y+i])return0;return1;}intinhash(intha,intwz){intw1;for(w1=last[ha];w1;w1=next[w1])if(jianyan(other[w1],wz))return0;w++;next[w]=last[ha];last[ha]=w;other[w]=wz;return1;}intmain(){freopen(1.in,r,stdin);freopen(1.out,w,stdout);scanf(%d%d,&n,&m);scanf(%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\n,ans);return0;}AC自动机#includecstdio#includecstring#includequeueusingnamespacestd;#defineN251000inttest,n,tot,ans,i;intjs[N],flag[N],g[N];inttrie[N][26];chars[1001000];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;queueintq;q.push(1);while(q.size()){x=q.front();q.pop();for(i=0;i26;i++){for(j=g[x];j;j=g[j])if(trie[j][i])break;if(y=trie[x][i])g[y]=j?trie[j][i]:1,q.push(y);elsetrie[x][i]=j?trie[j][i]:1;}}}voidac(intlen){inti,ch,x=1,j;for(i=1;i=len;i++){ch=s[i]-'a';x=trie[x][ch];for(j=x;j;j=g[j]){if(flag[j])break;ans+=js[j];flag[j]=1;}}}intmain(){freopen(1.in,r,stdin);freopen(1.out,w,stdout);scanf(%d,&test);while(test--){scanf(%d,&n);tot=1;ans=0;memset(trie,0,sizeof(trie));memset(flag,0,sizeof(flag));memset(js,0,sizeof(js));memset(g,0,sizeof(g));for(i=1;i=n;i++)scanf(%s,s+1),addtrie(strlen(s+1));bfs();scanf(%s,s+1);ac(strlen(s+1));printf(%d\n,ans);}return0;}后缀数组#includecstdio#includecstring#defineN10000chars[N];intheight[N],r[N],wa[N],wb[N],wc[N],wv[N],rank[N],sa[N];inttest,i,ans,len;intcmp(int*y,inta,intb,intl){returny[a]==y[b]&&y[a+l]==y[b+l];}voidda(int*r,int*sa,intn,intm){inti,j,p,*x=wa,*y=wb,*t;for(i=0;im;i++)wc[i]=0;for(i=0;in;i++)wc[x[i]=r[i]]++;for(i=1;im;i++)wc[i]+=wc[i-1];for(i=n-1;i=0;i--)sa[--wc[x[i]]]=i;for(j=1,p=1;pn;j*=2,m=p){for(p=0,i=n-j;in;i++)y[p++]=i;for(i=0;in;i++)if(sa[i]=j)y[p++]=sa[i]-j;for(i=0;ip;i++)wv[i]=x[y[i]];for(i=0;im;i++)wc[i]=0;for(i=0;ip;i++)wc[wv[i]]++;for(i=1;im;i++)wc[i]+=wc[i-1];for(i=n-1;i=0;i--)sa[--wc[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;in;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}}voidcalheight(int*r,int*sa,intn){inti,j,k=0;for(i=1;i=n;i++)rank[sa[i]]=i;for(i=0;in;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);}intmain(){freopen(1.in,r,stdin);freopen(1.out,w,stdout);scanf(%d,&test);while(test--){scanf(%s,s);len=strlen(s);s[len]='$';for(i=0;i=len;i++)r[i]=s[i];da(r,sa,len+1,128);calheight(r,sa,len);ans=len*(1+len)/2;for(i=2;i=len;i++)ans-=height[i];printf(%d\n,ans);}return0;}spfa#includecstdio#includecstring#includequeueusingnamespacestd;#defineN10000#defineM100000structedge{intn,o,j;}e[M];intn,m,i,x,y,z,w,j;intdist[N],flag[N],last[N];voidadd(intx,inty,intz){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].j=z;}voidspfa(intqi){intx,y,w1;queueintq;q.push(qi);memset(dist,42,sizeof(dist));dist[qi]=0;memset(flag,0,sizeof(flag));flag[qi]=1;while(q.size()){x=q.front();q.pop();flag[x]=0;for(w1=last[x];w1;w1=e[w1].n){y=e[w1].o;if(dist[x]+e[w1].jdist[y]){dist[y]=dist[x]+e[w1].j;if(flag[y]==0)flag[y]=1,q.push(y);}}}}intmain(){freopen(1.in,r,stdin);freopen(1.out,w,stdout);scanf(%d%d,&n,&m);for(i=1;i=m;i++)scanf(%d%d%d,&x,&y,&z),add(x,y,z),add(y,x,z);spfa(1);printf(%d\n,dist[n]);return0;}folyd#includecstdio#includecstring#definemax(x,y)xy?x:y#definemaxlongint2147483647usingnamespacestd;intf[101][101],max1,min1,i,j,k,m,n,x,y,w,ff[101];intmain(){while(scanf(%d,&n)&&n!=0){memset(f,42,sizeof(f));for(i=1;i=n;i++){f[i][i]=0;scanf(%d,&m);for(j=1;j=m;j++)scanf(%d%d,&x,&y),f[i][x]=y;}for(k=1;k=n;k++)for(i=1;i=n;i++)for(j=1;j=n;j++)if(f[i][k]+f[k][j]f[i][j])f[i][j]=f[i][k]+f[k][j];for(i=1;i=n;i++){max1=0;for(j=1;j=n;j++)max1=max(max1,f[i][j]);ff[i]=max1;}min1=maxlongint;for(i=1;i=n;i++)if(ff[i]min1)min1=ff[i],w=i;if(min1100000