KMP

大名鼎鼎的KMP算法，是一种在线性时间内能处理两个字符串的包含关系的算法，少废话，我们开始。

引入

给定两个字符串O和f，长度分别为n和m，
判断f是否在O中出现，如果出现则返回出现的位置。
常规方法是遍历O的每一个字符的位置，找到某一个字符刚好和f[0]相同，后，再从该位置开始和f进行匹配，但是这种方法的复杂度是O(nm)。
kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)

思想

我们首先用一个图来描述kmp算法的思想。

image
在字符串O中寻找f，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。
常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过了，所以效率不高。
事实上，如果我们提前计算某些信息，就有可能一次前移不止一位。
假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。看上图，我们可以得到如下的结论：

• A段字符串是f的一个前缀。
• B段字符串是f的一个后缀。
• A段字符串和B段字符串相等。

这就意味着，我们的算法最重要的是，计算字符串f每一个字符位置之前的字符串的前缀和后缀公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。
获得f每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串O比较。

分析

当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。事实上，字符串f的前移只是概念上的前移，只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。

image
看到这个图，自然就会想到，我们得计算next数组，怎么算呢？看着上图继续往下分析：
首先，next数组表示的是长度，下标从1开始；因为在遍历原字符串时，下标还是从0开始。假设我们现在已经求得next[1]、next[2]、……next[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求next[i+1]。

由上图我们可以看到，
如果位置i和位置next[i]处的两个字符相同（下标从零开始），则next[i+1]等于next[i]加1。
如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。
为什么呢？这是因为长度为next[i]前缀和后缀都可以分割成上图所示的构造，

如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。
如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。

看懂上面的图异常重要

模板

求一个字符串里有没有另一个字符串，一个字符串里有几个另一个字符串（可重叠和不可重叠两种）。

可重叠

#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])
{
    int q,k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q)
    {
        while(k > 0 && P[q] != P[k])
            k = next[k-1];
        if (P[q] == P[k])
        {
            k++;
        }
        next[q] = k;
    }
}

int kmp(const char T[],const char P[],int next[])
{
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);
    for (i = 0,q = 0; i < n; ++i)
    {
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i])
        {
            q++;
        }
        if (q == m)
        {
            printf("Pattern occurs with shift:%d\n",(i-m+1));
        }
    }    
}

int main()
{
    int i;
    int next[20]={0};
    char T[] = "ababxbababcadfdsss";
    char P[] = "abcdabd";
    printf("%s\n",T);
    printf("%s\n",P );
    // makeNext(P,next);
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i)
    {
        printf("%d ",next[i]);
    }
    printf("\n");
    return 0;
}

---

不可重叠

#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])
{
    int q,k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q)
    {
        while(k > 0 && P[q] != P[k])
            k = next[k-1];
        if (P[q] == P[k])
        {
            k++;
        }
        next[q] = k;
    }
}

int kmp(const char T[],const char P[],int next[])
{
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);
    for (i = 0,q = 0; i < n; ++i)
    {
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i])
        {
            q++;
        }
        if (q == m)
        {
            printf("Pattern occurs with shift:%d\n",(i-m+1));
            q = 0;
        }
    }
}

int main()
{
    int i;
    int next[20]={0};
    char T[] = "ababababa";
    char P[] = "aba";
    printf("%s\n",T);
    printf("%s\n",P );
    // makeNext(P,next);
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i)
    {
        printf("%d ",next[i]);
    }
    printf("\n");

    return 0;
}