擴大KMP算法(Extend KMP)。本站提示廣大學習愛好者：（擴大KMP算法(Extend KMP)）文章只能為提供參考，不一定能成為您想要的結果。以下是擴大KMP算法(Extend KMP)正文
擴大kmp既是求形式串和主串的每個後綴的最長公共前綴
即令s[i]表現主串中以第i個地位為肇端的後綴，則B[i]表現s[i]和形式串的最長公共前綴
明顯KMP是求s[i]=形式串長度的情形，所以，擴大KMP是對KMP的拓展
像求KMP的next數組一樣，我們先求A[i]，表現形式串的後綴和形式串的最長公共前綴
然後再應用A[i]求出B[i]
解釋一下A的求法，B同理
如今我們請求A[i]，且A[1]---A[i-1]曾經求出，設k，且1<=k<=i-1，並知足k+A[k]最年夜
所以T[k]--T[k+A[k]-1]=T[0]--T[A[k]-1]，推出T[i]--T[k+A[k]-1]=T[i-k]--T[A[k]-1]
令L=A[i-k]，若L+i-1<k+A[k]-1，由A是最長公共前綴知A[i]=L，不然，向後婚配，曉得字符串掉配
並響應更新k
時光龐雜度為線性O(m+n)
while(1+j<strlen(T)&&T[0+j]==T[1+j])
j = j + 1;
A[1]=j;
int k=1;
for(int i=2; i<strlen(T); i++)
{
int Len = k + A[k] - 1,L = A[i-k];
if( L < Len - i + 1 )
A[i] = L;
else
{
j = max(0,Len -i +1);
while(i+j<strlen(T)&&T[i+j] == T[0+j])
j = j + 1;
A[i] = j,k = i;
}
}
j = 0;
while(j<strlen(S)&&j<strlen(T)&&T[0+j]==S[0+j])
j = j + 1;
B[0] = j,k = 0;
for(int i=1; i<strlen(S); i++)
{
int Len = k + B[k] - 1,L = A[i-k];
if( L < Len - i + 1 )
B[i] = L;
else
{
j = max(0,Len -i +1);
while(i+j<strlen(S)&&j<strlen(T)&&S[i+j] == T[0+j])
j = j + 1;
B[i] = j,k = i;
}
}
ps:通俗的next是到這個開頭的，能和形式串婚配的長度，擴大kmp是以這個開首的能婚配的最年夜長度
pss:然後我簡略比擬了下kmp和擴大kmp http://www.isnowfy.com/kmp-and-extend-kmp/
