KMP算法

KMP所解决的问题：判断一个串是否是另一个串的子串。
例如：

给两个字符串S1和S2，问S2是否是S1的子串？
数据范围：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

注：一个字符串的子串指的是字符串某一段连续的部分（比如第一个例子），可以是其本身。
而不连续的部分，一般称作为子序列！（比如第二个例子，ABB是ABAAB的子序列而不是子串）

通常做法：
暴力求解

暴力求解.png
暴力求解虽然可以计算出来，但是其时间复杂度往往是不允许的
时间复杂度：O(|S1||S2|)
当|S1|=|S2|=100000时，|S1||S2|=10000000000 也就是十个0，100亿！！
用超级计算机还是有希望1s跑完的(●ˇ∀ˇ●)

暴力匹配不能快速解决，有更好的办法吗？
有！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），很容易发现字符串S前缀后缀最大值为5，即ABABA。

②next[ ]数组
知道了最大前缀后缀的定义，现在就要想办法把每个字符所在位置的最大前缀后缀记录下来，这里用的是next[ ]。

NEXT数组.png

next的数组构建

int init[1000005];//原始字符串
int pp[1000005];//匹配字符串
int Next[1000005];//next数组
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数组
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;
}

以上模版转自fold2（http://www.jianshu.com/p/fdd43ae2892f?utm_campaign=maleskine&utm_content=note&utm_medium=reader_share&utm_source=weibo）