首页 > 代码库 > 常用字符串算法
常用字符串算法
简介
字符串的处理几乎无处不在，常用的字符串算法有KMP、扩展KMP、Trie树、AC自动机、Manacher、哈希、SA、SAM等。
Knuth-Morris-Pratt 算法
给你两个字符串AB，询问B串是否是A串的子串（A串是否包含B串）。
可以枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。
而KMP算法能够在线性复杂度内求出一个串在另一个串的所有匹配位置。
KMP的核心思想在于构建一个前缀数组（失配数组），对于模式串P，假设字符串下标从1开始，数组F满足F[i]=max{j|j<i且P[1..j]=P[i-j+1..i}，即P的长度为j的前缀等于P的长度为i的前缀的长度为j的后缀。这说明F[i]所求的是串P[1..i]的一个最长的前缀P[1..j]，这个前缀也是它的后缀。当这个前缀找不到的时候，F[i]设为0。
例如P=ababc，则F[4]=2，因为ab(P[1..2])是abab(P[1..4])的最长的前缀，又是它的后缀ab(P[3..4])。
有了F数组，就可以匹配两个字符串，主串T与模式串P。
先求出P的F数组，然后维护两个下标i和j，表示当前模式串P的前j个字符与主串T在位置i的前j个字符匹配，即P[1..j]=T[i-j+1..i]。
当算法在尝试对T[i+1]和P[j+1]匹配时，发现它们字符不同，那么就用F数组进行跳跃，使j=F[j]。
KMP算法高效的原因在于充分利用了匹配中的已有信息。关键的一步在于T[i+1]!=P[j+1]时j=F[j]。
因为我已知P[1..j]=T[i-j+1..i]而P[1..F[j]]=P[j-F[j]+1..j]，因此P[1..F[j]]=T[i-F[j]+1..i]，所以我们可以直接从F[j]位置开始继续匹配。
在实际实现中，字符串的下标从0开始，而我们仍然定义F数组的下标从1开始，对代码做一些简单的调整即可。
1 const int maxn=1111111; 2 char P[maxn]; 3 char T[maxn]; 4 int f[maxn]; 5 6 void getFail(char P[],int f[]){ 7 int i=0,j=-1; 8 int len=strlen(P); 9 f[0]=-1;10 while (i<len){11 if (j==-1||P[i]==P[j]){12 i++,j++;13 f[i]=j;14 }15 else{16 j=f[j];17 }18 }19 }20 21 void KMP(char T[],char P[],int f[]){22 int i=0,j=0;23 int n=strlen(T);24 int m=strlen(P);25 getFail(P,f);26 while(i<n){27 if(j==-1||T[i]==P[j]){28 i++,j++;29 }30 else{31 j=f[j];32 }33 if(j==m){34 // TO DO:35 //ans++;36 j=f[j];37 }38 }39 }
一些练习题
POJ 3461 Oulipo
计算单词W在整篇文章T中出现的次数。
KMP最基本的应用，统计出现次数，套模板即可。
1 if(j==m){2 // TO DO:3 ans++;4 j=f[j];5 }
POJ 2752 Seek the Name, Seek the Fame
找到一个S的子串作为前缀-后缀字符串。所谓前缀-后缀字符串即S的子串不仅是S的前缀又是S的后缀。
子串s[ 1 -> f[n] ] 是最长的子串，既是是s的前缀又是s的后缀，同理1 -> f[ f[n] ] 是次短的...依次递归。
1 while (f[n]>0){2 stk.push(f[n]);3 n=f[n];4 }
POJ 2406 Power Strings
输出最大的n使得s由a重复n次而成。
当 n%(n-f[n])==0时，n-f[n] 是s最短的循环节。
1 if (n%(n-f[n])==0){2 printf("%d\n",n/(n-f[n]));3 }4 else{5 printf("1\n");6 }
POJ 1961 Period
对每个前缀i，若能由某些字符重复k次形成，输出最大的k。
与上题类似，枚举i，若i%(i-f[i])==0 则最短循环节为i-f[i]，k为i/(i-f[i])
1 for (int i=2;i<=n;i++){2 if (f[i]>0&&i%(i-f[i])==0){3 printf("%d %d\n",i,i/(i-f[i]));4 }5 }
HDU 3336 Count the string
求出s有多少个子串是它本身的前缀。
DP公式如下。
1 for (int i=1;i<=n;i++){2 dp[i]=dp[f[i]]+1;3 ans=(ans+dp[i])%10007;4 }
HDU 3746 Cyclic Nacklace
至少要在字符串s后面补几个字符才能凑成一个循环。
若本身已经有循环节，则答案为0。
1 if (f[n]>0&&n%(n-f[n])==0) printf("0\n");2 else printf("%d\n",n-f[n]-n%(n-f[n]));
HDU 2087 剪花布条
给定T和P，为T中能分出几块P。
只匹配一次的KMP。当匹配成功时将j置为0即可。
1 if(j==m){2 // TO DO:3 ans++;4 j=0;5 }
HDU 2594 Simpsons’ Hidden Talents
求a的最长前缀是b的后缀。
将两串拼接成s，a在前b在后，则问题转化为求一个串的前缀是后缀。
注意s的前缀不一定是a的前缀也不一定是b的后缀，所以当f[n]>na或f[n]>nb时我们要忽略子串s[ 1->f[n] ]。
1 while (f[m]>n1||f[m]>n2){ 2 m=f[m]; 3 } 4 if (f[m]>0){ 5 for (int i=0;i<f[m];i++){ 6 printf("%c",s1[i]); 7 } 8 printf(" %d\n",f[m]); 9 }10 else{11 printf("0\n");12 }
hdu 4763 Theme Section
求出满足EAEBE格式的最长子串E的长度。
由最长前缀后缀推广而来。
首先由大到小枚举前缀后缀，对于每个前缀后缀f[x]，在字符串中间寻找f[i]=f[x]，若找到则输出答案，否则继续枚举。
1 int x=n; 2 bool flag=false; 3 while (f[x]>(n/3)) x=f[x]; 4 while (f[x]>0){ 5 flag=false; 6 for (int i=f[x]*2;i<=n-f[x];i++){ 7 if (f[i]==f[x]){ 8 flag=true; 9 break;10 }11 }12 if (flag) break;13 }14 if (!flag) printf("0\n");15 else printf("%d\n",f[x]);
扩展 KMP 算法
给定主串S和模板串T，扩展KMP问题要求解的就是extend[1..|S|]，其中extend[i]表示S[i..|S|]与T的最长公共前缀，即S中的每个后缀与T的最长公共前缀的长度。
对比KMP算法，发现当extend[i]=|T|时，T恰好在S中出现。因此该算法是KMP算法的进一步扩展，称为扩展KMP算法。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int MM=100005; 6 int next[MM],extand[MM]; 7 char S[MM],T[MM]; 8 void GetNext(const char *T){ 9 int len=strlen(T),a=0;10 next[0]=len;11 while(a<len-1 && T[a]==T[a+1]) a++;12 next[1]=a;13 a=1;14 for(int k=2;k<len;k++){15 int p=a+next[a]-1,L=next[k-a];16 if( (k-1)+L >= p){17 int j = (p-k+1)>0 ? (p-k+1) : 0;18 while(k+j<len && T[k+j]==T[j]) j++;19 next[k]=j;20 a=k;21 }22 else23 next[k]=L;24 }25 }26 void GetExtand(const char *S,const char *T){27 GetNext(T);28 int slen=strlen(S),tlen=strlen(T),a=0;29 int MinLen = slen < tlen ? slen : tlen;30 while(a<MinLen && S[a]==T[a]) a++;31 extand[0]=a;32 a=0;33 for(int k=1;k<slen;k++){34 int p=a+extand[a]-1, L=next[k-a];35 if( (k-1)+L >= p){36 int j= (p-k+1) > 0 ? (p-k+1) : 0;37 while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;38 extand[k]=j;39 a=k;40 }41 else42 extand[k]=L;43 }44 }45 int main(){46 while(scanf("%s%s",S,T)==2){47 GetExtand(S,T);48 for(int i=0;i<strlen(T);i++)49 printf("%d ",next[i]);50 puts("");51 for(int i=0;i<strlen(S);i++)52 printf("%d ",extand[i]);53 puts("");54 }55 return 0;56 }
一些练习题
HDU 4333 Revolving Digits
读入数字串P，T由两个P拼接而成。
则T从0到n的每个长度为n的后缀即为一种数字排列。
对于T的后缀i，设其与原数字P的最长公共前缀长度为L。
若L>=n，说明此后缀表示的数与原数字相等。
若L<n，则令 T[i+extand[i]] 与 P[extand[i]] 比较大小即可得出两数的大小。
对于类似123123形式的重复串，排列三次以后又回到了123123的形式，所以答案必须除以循环节。
用KMP的找到最小循环节个数n/(n-f[n])
1 scanf("%s",P); 2 strcpy(T,P); 3 strcat(T,P); 4 GetExtand(T,P); 5 int n=strlen(P); 6 int cnt1=0,cnt2=0,cnt3=0; 7 for (int i=0;i<n;i++){ 8 if (extand[i]>=n) cnt2++; 9 else if (T[i+extand[i]]<P[extand[i]]) cnt1++;10 else cnt3++;11 }12 getFail(P,f);13 int tol=1;14 if (n%(n-f[n])==0) tol=n/(n-f[n]);15 printf("Case %d: %d %d %d\n",++Cas,cnt1/tol,cnt2/tol,cnt3/tol);
HDU 4300 Clairewd’s message
给一个密文到明文的映射表
给一个串，前面为密文，后面为明文，密文一定是完整的，但明文不完整或没有
将这个串补全。
令原串为T，将原串全部翻译为P。
可以发现原串T的后缀i是P的前缀。
从(n+1)/2开始枚举T的后缀，对于每个后缀i，若i+extand[i]>=n则从T：0~i-1为密文，P：i~n-1为明文。
1 GetExtand(T,P); 2 int ret=len; 3 for (int i=(len+1)/2;i<len;i++){ 4 if (extand[i]+i>=len){ 5 ret=i; 6 break; 7 } 8 }
Trie 树
Aho-Corasick 自动机
Manacher 算法
字符串哈希
后缀数组
后缀自动机