KMP所解決的問題：判斷一個串是否是另一個串的子串。
例如：

給兩個字符串S1和S2匀伏，問S2是否是S1的子串洒忧？
數(shù)據(jù)范圍：0<|S2|<=|S1|<=100000

Input
第一行輸入一個字符串S1，第二行輸入一個字符串S2够颠，保證0<|S2|<=|S1|<=100000

Output
如果S2是S1的子串熙侍，輸出“YES”.
否則，輸出“NO”.

樣例
Sample Input
AAABAAABAAABAAAD
AAABAAAD

ABAAB
ABB

Sample Output
YES
NO

注：一個字符串的子串指的是字符串某一段連續(xù)的部分（比如第一個例子），可以是其本身核行。
而不連續(xù)的部分牢硅，一般稱作為子序列！（比如第二個例子芝雪，ABB是ABAAB的子序列而不是子串）

通常做法：
暴力求解

暴力求解.png

暴力匹配不能快速解決堡牡，有更好的辦法嗎？
有杨刨！KMP算法晤柄！

①前綴后綴最大值：
一個長度為N的字符串S，它有N+1個前綴（包括空前綴）和N+1個后綴（包括空后綴）
比如ABC妖胀，有4個前綴芥颈，空，A赚抡，AB爬坑，ABC
有4個后綴，空涂臣，C盾计，BC，ABC
比如AAA赁遗，有4個前綴署辉，空，A岩四，AA哭尝，AAA
有4個后綴，空炫乓，A刚夺，AA，AAA

前綴與后綴

如果不算自身（ABABABA）末捣，很容易發(fā)現(xiàn)字符串S前綴后綴最大值為5侠姑，即ABABA。

②next[ ]數(shù)組
知道了最大前綴后綴的定義箩做，現(xiàn)在就要想辦法把每個字符所在位置的最大前綴后綴記錄下來莽红，這里用的是next[ ]。

NEXT數(shù)組.png

next的數(shù)組構(gòu)建

int init[1000005];//原始字符串
int pp[1000005];//匹配字符串
int Next[1000005];//next數(shù)組
int m,n;//m=strlen(init);n=strlen(pp);
void creat_next(void)
{
    int j=0;
    next1[0]=0;
    for(int i=1; i<n; i++)
    {
        if(pp[i]==pp[j])
        {
            Next[i]=Next[i-1]+1;
            j++;
        }
        else
        {
            while(1)
            {
                if(j!=0)j=Next[j-1];
                else break;
                if(pp[i]==pp[j])
                {
                    Next[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

NEXT.png

對比下

NEXT.png

Number Sequence：

int ys[1000005];//原始字符串
int pp[1000005];//匹配字符串
int next1[1000005];//next數(shù)組
int m,n;//m=strlen(ys);n=strlen(pp);
void findnext(void)
{
    int j=0;
    next1[0]=0;
    for(int i=1; i<n; i++)
    {
        if(pp[i]==pp[j])
        {
            next1[i]=next1[i-1]+1;
            j++;
        }
        else
        {
            while(1)
            {
                if(j!=0)j=next1[j-1];
                else break;
                if(pp[i]==pp[j])
                {
                    next1[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

int kmp(void)
{
    int i=0,j=0;
    findnext();
    while(i<m)
    {
        if(ys[i]==pp[j])
        {
            i++;j++;
            if(j==n)return i-n+1;
        }
        else if(j>0)j=next1[j-1];
        else if(j==0)i++;
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&m,&n);
        for(int i=0;i<m;i++)
            scanf("%d",&ys[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&pp[i]);
        int ans=kmp();
        printf("%d\n",ans);
    }
    return 0;
}

Oulipo

int m,n;
int nex[1000005];

void findnext(char *pp)
{
    memset(nex,0,sizeof(nex));
    int j=0;
    nex[0]=0;
    for(int i=1; i<n; i++)
        if(pp[i]==pp[j])
        {
            nex[i]=nex[i-1]+1;
            j++;
        }
        else
            while(1)
            {
                if(j!=0)j=nex[j-1];
                else break;
                if(pp[i]==pp[j])
                {
                    nex[i]=j+1;
                    j++;
                    break;
                }
            }
}

int kmp(char *ys,char *pp)
{
    int i=0,j=0,ans=0;
    while(i<m)
    {
        if(ys[i]==pp[j])
        {
            i++;
            j++;
            if(j==n)ans++;
        }
        else if(j>0)j=nex[j-1];
        else if(j==0)i++;
    }
    return ans;
}

int main()
{
    char pp[10005];
    char ys[1000005];
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",pp);
        n=strlen(pp);
        findnext(pp);
        scanf("%s",ys);
        m=strlen(ys);
        printf("%d\n",kmp(ys,pp));
    }
    return 0;
}

以上模版轉(zhuǎn)自fold2（http://www.reibang.com/p/fdd43ae2892f?utm_campaign=maleskine&utm_content=note&utm_medium=reader_share&utm_source=weibo）