首页 > 代码库 > 扩展KMP
扩展KMP
给定串S和T，求S的每一个后缀和T的最长公共前缀。
方法1：暴力算法，时间复杂度O(n^2);
方法2:后缀数组，利用height的性质可以求出该问题，时间复杂度为O(n),但是预处理为O(nlogn)
方法3:扩展KMP，充分利用已经匹配过的性质，降低匹配的时间,时间复杂度为O(n)
学习资料：http://www.docin.com/p-423302546.html
设next[i]为这样一个数组，next[i]为串T的suffix(i)和suffix(0)的相似度，假设next[0-->k-1]已经算出了，并且在以前的匹配中，
匹配到的最远处为p，如图 
假设是suffix(a)和suffix(0)匹配到最远处p，那么有T[a-->p] == T[0-->p-a+1]那么这个匹配的后面一段也相等，即T[k-->p]==T[k-a-->p-a+1],
又因为next[k-a]是已知的,令L = next[k-a]
有两种情况，
①k+L-1 < p， 那么next[k] = L,不可能大于L，否则next[k-a] 就不等于L了， 可能有人会想到，为什么表示k+L-1<=p，这个因为，如果取等号，那么p+1的部分没被判断过，所以不能直接next[k] = L;
②K+L-1>=p, 那么要重新匹配超过p的部分，即T[p+1] 和T[p-k+1]重新匹配。
九度oj 1535
1 /*next[i] 表示T[i-->n]和T[0-->n]的相似度 2 */ 3 4 #include <stdio.h> 5 #include <string.h> 6 const int N = 1000000 + 10; 7 char S[N],T[N]; 8 int next[N]; 9 int extend[N];10 void makeNext()11 {12 int n,a,j,k,L,p;13 next[0] = n = strlen(T);14 a = 0;15 while(a+1<n && T[a]==T[a+1]) a++;16 next[1] = a;17 a = 1;18 for(k=2; k<n; ++k)19 {20 p = a + next[a] - 1;21 L = next[k-a];22 if(k+L-1>=p)23 {24 //这一切都要求p>=k,否则，从新从0开始匹配。25 j = p - k + 1 > 0 ? p-k+1 : 0;26 while(k+j<n && T[k+j]==T[j]) ++j;27 next[k] = j;28 a = k;29 }30 else31 next[k] = L;32 33 }34 35 }36 void makeExtend()37 {38 int sLen = strlen(S),tLen = strlen(T);39 int len = sLen < tLen ? sLen : tLen;40 int a = 0,k,j,L,p;41 while(a<len && S[a]==T[a]) a++;42 extend[0] = a;43 a = 0;44 for(k=1; k<sLen; ++k)45 {46 p = a + extend[a] -1;47 L = next[k-a];48 if(k+L-1>=p)49 {50 j = p-k+1>0?p-k+1:0;51 while(k+j<sLen&&j<tLen &&S[k+j]==T[j])52 j++;53 extend[k] = j;54 a = k;55 }56 else57 extend[k] = L;58 }59 }60 int main()61 {62 while(scanf("%s%s",S,T)!=EOF)63 {64 makeNext();65 makeExtend();66 int n = strlen(S);67 int ans = 0;68 for(int i=0; i<n; ++i)69 if(extend[i] == n - i)70 {71 ans = extend[i];72 break;73 }74 printf("%d\n",ans);75 }76 return 0;77 }
扩展KMP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。