詳解：https://www.cnblogs.com/yjiyjige/p/3263858.html
https://blog.csdn.net/lee18254290736/article/details/77278769
字符串匹配的暴力方法與KMP的比較：
遇到以下情況時(shí)：
image.png
-
暴力方法把匹配的指針下移一位
image.png -
KMP根據(jù)next數(shù)組跳過(guò)不需要遍歷的部分：
image.png
KMP的思想：
利用已經(jīng)部分匹配這個(gè)有效信息，保持i指針不回溯，通過(guò)修改j指針，讓模式串盡量地移動(dòng)到有效的位置。
推理：
當(dāng)T[i] != P[j]時(shí)
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]
PS:為什么是i-k~i-1而不是i-k~i-x(x>1)？
因?yàn)槿绻莍-k~i-x的話說(shuō)明就算j移到i-k還是無(wú)法匹配i-x~i-1這段字符串，所以必須以i-k開(kāi)頭i-1結(jié)尾。
image.png
next數(shù)組的含義：(next數(shù)組由匹配串ABCE自己生成)
當(dāng)j位失配時(shí)，j需要回退到的地方，即next[j]。（j是pattern對(duì)應(yīng)的指針）
next數(shù)組如何定義？又如何判斷要跳過(guò)多少元素呢？
Next[0]==Next[1]== -1是默認(rèn)值，但是在處理中第一位pattern[0]不匹配時(shí)要i++，其他只需要j=0即可。如果pattern[i]不匹配，則將j指針指向Next[i]=2，即j=Next[]；
Next數(shù)組的寫(xiě)法：
// 當(dāng)?shù)趎位不匹配時(shí)怎么跳。
void getnext(char pattern[]){
int i=0,j=0,k=0;
// 事先約定好的兩位
Next[0]=-1;
// 第一位不跳，-1位不存在匹配的情況。
Next[1]=-1;
// 第二位不匹配，但第一位匹配，移動(dòng)一位。比如ab與ac不匹配，肯定將i移動(dòng)到b后面。
for(i=2;i<strlen(pattern);i++){
// 從pattern[2]開(kāi)始不匹配時(shí)
Next[i]=-1;
for(j=i-2;j>=0;j--){
// j的結(jié)束位置從[0,i-2]，開(kāi)始位置默認(rèn)0的貼前字符串
for(k=0;k<=j;k++){
// [0,i-2]的貼后字符串
//cout<<"i:"<<i<<" k:"<<k<<" "<<pattern[k]<<" j:"<<j<<" "<<pattern[i-1-j+k]<<endl;
if(pattern[k]==pattern[i-1-j+k]){
}
else{
break;
}
}
if(k==j+1){
Next[i]=j+1;
// 最長(zhǎng)的匹配子串長(zhǎng)度(0-j),所以長(zhǎng)度是j+1
break;
}
}
}
}
image.png
在k的循環(huán)體里面：
image.png
Next數(shù)組基礎(chǔ)上的kmp:
void kmp(char text[],char pattern[]){
int i=0,j=0;
int t=strlen(text);
int p=strlen(pattern);
bool pass=false;
while(i<t){
// 只要看text的指針有沒(méi)有越界即可，反正pattern的指針j越界就會(huì)跳出循環(huán)匹配成功
//cout<<i<<" "<<j<<" "<<Next[j]<<endl;
if(text[i]==pattern[j]){
i++;
j++;
}
else{
if(Next[j]==-1&&j==0){
// 如果沒(méi)有找到串內(nèi)重復(fù)的串，只需要將pattern的指針指向開(kāi)頭就好。
// ab與ac如果把j=0，會(huì)陷入死循環(huán)。
i++;
}
else if(Next[j]==-1){
j=0;
}
else{
// 如果匹配失敗，將j指針指向Next[j]對(duì)應(yīng)的地址。
j=(Next[j]);
}
}
if(j==strlen(pattern)){
pass=true;
cout<<"\nmatch: ["<<i-strlen(pattern)<<","<<i-1<<"]"<<endl;
show(text,i-strlen(pattern),i-1);
}
}
if(!pass)cout<<"\nNo matching"<<endl;
}
