很有啟發(fā)的幾篇文章：
文章傳送門：
文章一：KMP算法的Next數(shù)組詳解
文章二：從頭到尾徹底理解KMP
文章三：字符串匹配的KMP算法
首先說(shuō)說(shuō)字符串模式匹配問(wèn)題：
問(wèn)題描述：子串的定位操作通常稱作串的模式匹配，即查找子串在主串中的位置。我們把主串稱為S，子串稱作模式串T，用 i 和 j 指示主串S和模式串T中當(dāng)前正待比較的字符位置。
算法基本思想：從主串S的第pos個(gè)字符起和模式的第一個(gè)字符比較之，若相等，則繼續(xù)逐個(gè)比較下個(gè)字符(pos值不變)；若不相等,從主串的pos++個(gè)字符起再重新和模式串的第一個(gè)字符比較。依次類推，直到模式串T中的每個(gè)字符依次和主串S中的一個(gè)連續(xù)的字符序列相等，則匹配成功，函數(shù)值為主串里的匹配串第一個(gè)字符在主串中的序號(hào)，若匹配不成功，函數(shù)值返回0.
上圖：

image

數(shù)據(jù)結(jié)構(gòu)描述：

//求子串位置的定位函數(shù) Index(S,T,pos)
int Index(SString S,SString T,int pos){
    //返回子串T在主串中第pos個(gè)字符之后的位置。若不存在，則函數(shù)值為0.
    //其中，T非空，1<=pos<=StrLength(S)
    i=pos;j=1;
    while(i<=S[0]&&j<=T[0]){
        if(S[i]==T[j]){//繼續(xù)比較后續(xù)字符
            i++;
            j++;
        }
        else{//指針后退重新開(kāi)始匹配
            i=i-j+2;
            j=1;
        }
    }
    if(j>T[0])return i-T[0];
    else return 0;
}//Index

代碼：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string S,T;//S是主串，T為模式串
    cin>>S>>T;
    int pos=0,flag=0,ans=-1;//flag==1，則匹配成功
    while(1){
        int i=pos;//i是主串的位置指針
        if(S.size()-i<T.size()){
            break;
        }
        for(int j=0;j<T.size();j++){//j是模式串的位置指針
            if(S[i]==T[j]){
                i++;
                if(j==T.size()-1){
                    flag=1;
                    ans=pos+1;//S下標(biāo)是從零開(kāi)始，故ans在pos基礎(chǔ)上加1
                    break;
                }
                continue;
            }
            else{
                pos++;
                break;
            }
        }
        if(flag==1){
            break;
        }      
    }
    cout<<ans<<endl;
    return 0;
}

KMP算法介紹：
這個(gè)算法是由高德納和沃恩·普拉特在1974年構(gòu)思，同年詹姆斯·H·莫里斯也獨(dú)立地設(shè)計(jì)出該算法，最終由三人于1977年聯(lián)合發(fā)表。這種算法被稱為 Knuth-Morris-Pratt 操作，簡(jiǎn)稱為 “KMP算法”，常用于在一個(gè)文本串S內(nèi)查找一個(gè)模式串P 的出現(xiàn)位置。

上圖：

image

顯然，KMP算法改進(jìn)之處在于，每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符比較不等時(shí)，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右”滑動(dòng)“盡可能遠(yuǎn)的一段距離后繼續(xù)進(jìn)行比較。那么問(wèn)題來(lái)了，模式串向右“滑動(dòng)”的可行距離多遠(yuǎn)，即當(dāng)主串中第 i 個(gè)字符與模式中第 j 個(gè)字符比較不等時(shí)，主串中第 i 個(gè)字符應(yīng)與模式串中哪個(gè)字符進(jìn)行比較？（注意, i 不回溯。）

由此引出數(shù)組:
令;則表明當(dāng)模式串中第個(gè)字符與主串第個(gè)字符“失配”時(shí)，在模式串中需重新和主串中該字符進(jìn)行比較的字符的位置。即就是模式串向右“滑動(dòng)”的距離。所以問(wèn)題在于如何求數(shù)組？

引出前綴和后綴：假設(shè)主串''，模式串為''，并假設(shè)此時(shí)應(yīng)與模式串中第個(gè)字符繼續(xù)比較，則模式串中前個(gè)字符的子串必須滿足關(guān)系式,且不可能存在滿足下列關(guān)系式
''=''
已經(jīng)得到的“部分匹配”的結(jié)果是
''=''
由式和式推得下列等式
''=''
式子用文字描述：
模式串中存在兩個(gè)相同的子串，該子串以模式串的第一個(gè)字符為首字符，長(zhǎng)度為，就是"前綴"和"后綴"的最長(zhǎng)的共有元素的長(zhǎng)度。"前綴"指除了最后一個(gè)字符以外，一個(gè)字符串的全部頭部組合；"后綴"指除了第一個(gè)字符以外，一個(gè)字符串的全部尾部組合。
舉例：

image

－　"A"的前綴和后綴都為空集，共有元素的長(zhǎng)度為0；
－　"AB"的前綴為[A]，后綴為[B]，共有元素的長(zhǎng)度為0；
－　"ABC"的前綴為[A, AB]，后綴為[C,BC]，共有元素的長(zhǎng)度0；
－　"ABCD"的前綴為[A, AB, ABC]，后綴為[D,CD,BCD]，共有元素的長(zhǎng)度為0；
－　"ABCDA"的前綴為[A, AB, ABC, ABCD]，
后綴為[A,DA,CDA,BCDA]，共有元素為"A"，長(zhǎng)度為1；
－　"ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為 [B,AB,DAB,CDAB,BCDAB]，共有元素為"AB"，長(zhǎng)度為2；
－　"ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[D,BD,ABD,DABD,CDABD,BCDABD]，共有元素的長(zhǎng)度為0。

求數(shù)組的代碼：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int nxt[maxn];
void getNext(string p){
    // 初始條件
    int j=0;
    int k=-1;
    nxt[0]=-1; 
    // 根據(jù)已知的前j位推測(cè)第j+1位
    while(j<p.size()-1){//p[k]表示前綴，p[j]表示后綴
        if(k==-1||p[j]==p[k])nxt[++j]=++k;
        else k=nxt[k];       
    }
}
int main(){
    string p;
    cin>>p;
    getNext(p);
    for(int i=0;i<p.size();i++)
        cout<<nxt[i]<<' ';
    cout<<endl;
    return 0;
}

運(yùn)行：

nxt.png

改進(jìn)：

void getNext(string p){
    // 初始條件
    int j=0;
    int k=-1;
    nxt[0]=-1; 
    // 根據(jù)已知的前j位推測(cè)第j+1位
    while(j<p.size()-1){//p[k]表示前綴，p[j]表示后綴
        if(k==-1||p[j]==p[k]){
            ++j;
            ++k;
            if(p[j]!=p[k])nxt[j]=k;//優(yōu)化
            else nxt[j]=k;
        }
        else k=nxt[k];       
    }
}

改進(jìn)原因：當(dāng)p[j] != s[i] 時(shí)，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然導(dǎo)致后一步匹配失?。ㄒ?yàn)閜[j]已經(jīng)跟s[i]失配，然后你還用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很顯然，必然失配），所以不能允許p[j] = p[ next[j ]]。如果出現(xiàn)了p[j] = p[ next[j] ]咋辦呢？答案是需要再次遞歸，即令next[j] = next[ next[j] ]。
如圖：
!=注意 ==

image

完整版算法

#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int nxt[maxn];
string s,p;
void getNext(string p){
    // 初始條件
    int j=0;
    int k=-1;
    nxt[0]=-1; 
    // 根據(jù)已知的前j位推測(cè)第j+1位
    while(j<p.size()-1){//p[k]表示前綴，p[j]表示后綴
        if(k==-1||p[j]==p[k]){
            ++j;
            ++k;
            if(p[j]!=p[k])nxt[j]=k;//優(yōu)化
            else nxt[j]=k;
        }
        else k=nxt[k];       
    }
}
int kmp(int lens,int lenp){
    int i=0,j=0,ans=-1;//如果最后ans==1,則匹配失敗
    while(i<lens&&j<lenp){
        if(j==-1||s[i]==p[j]){
            i++;
            j++;
        }
        else j=nxt[j];
        if(j==lenp)return ans=i-lenp+1;//習(xí)慣上第一個(gè)字符下標(biāo)為1
    }
    return ans;
}
int main(){
    //string s,p;
    cin>>s>>p;
    memset(nxt,-1,sizeof(nxt));
    getNext(p);
    int lens=s.size();
    int lenp=p.size();
    int ans=kmp(lens,lenp);
    cout<<ans<<endl;
    return 0;
}