4.1
string A,B; //采用類似于kmp算法中求next數(shù)組的情況，只不過這次next數(shù)組保存的是最長前綴和后綴的值
int next[B.length()+1];
if(B[0]==A[0])
next[0]=1;//先初始化第一個值如果相同就l=1绑洛，否則l=0
else
next[0]=0;
int k=next[0];
int m=B.length();
for(int i=1;i<m;i++)
{
if(B[i]=A[k])//如果相等l值加1
next[i]=next[i-1]+1;
else//不相等就移位比較
{
while(k>0&&B[i]!=A[k])
{
k=next[k];
}
k++;
next[i]=k;
}
}
int result=next[B.length()-1];//最終結(jié)果就為next數(shù)組最后一個值
算法的復(fù)雜度為O（n）
4.2
非優(yōu)化算法：
當(dāng)p[k]=p[j]時熬苍，最長前綴和最長后綴都加一，next[i]=k+1正確皂林；
若p[k]!=p[j],此時將p作為目標(biāo)，第k個失配蚯撩，便要將串向右移础倍，讓p[next[k]]來跟p[i]匹配，便是遞歸過程胎挎，直到二者相等或者k等于零
優(yōu)化算法：
在非優(yōu)化算法的基礎(chǔ)上著隆，若p[i]==p[k],在p[i]跟T[j]失配時，因為按照非優(yōu)化算法呀癣，p需要右移使p[k]跟T[j]相匹配美浦，但是由于p[i]等于p[k]所以p[k]必定失配，所以需要再右移使得p[next[k]]來配项栏，故next[i]=next[k]合理
