字符串，模式匹配，KMP算法

　　KMP算法，用于在一个字符串S中查找一个模式串P 的出现位置，算法复杂度为O(n+m)。

　　当模式串P中的第j个字符跟字符串S中的第i个字符匹配失配时，i不回溯，模式串向右滑动最大K个字符位置，其第K+1的位置的字符与字符串S的第i个字符继续匹配，匹配了，i++，不匹配，模式串再向右滑动最大K个字符位置，依次类推。如何确定每次滑动的K的数值，这就是next数组。

　　下图，在模式串P的第j位与字符串S字符匹配失配的时候，可以看出，P第0位至第j-1位的字符串（与字符串S匹配的部分）的最大前缀字符串P的0~P的k-1与最大后缀字符串P的j-k~P的j-1相等（ 前后缀从左向右对应相等，且有可能重叠部分字符，比如P[0~2] == P[2~4] ），与主字符串S无关。

　　依据上述特性，可以计算出模式串第0~m-1，每个位置失配的时候的最大K（即模式串P向右滑动的最大值）放入next数组。

 

 

#include <iostream>
#include <string>
#include <cassert>
using namespace std;

int KMPStrMatching(string S, string P, int *N, int start) 
{
    int j= 0; // 模式的下标变量
    int i = start; // 目标的下标变量
    int pLen = P.length( ); // 模式的长度
    int tLen = S.length( ); // 目标的长度
    if (tLen - start < pLen) // 若目标比模式短，匹配无法成功
        return (-1);
    while ( j < pLen && i < tLen) 
    { // 反复比较，进行匹配
        if ( j == -1 || S[i] == P[j])
            i++, j++;
        else j = N[j];
    }
    if (j >= pLen)
        return (i-pLen); // 注意仔细算下标
    else return (-1);
}

int* findNext(string P) 
{
    int j, k;
    int m = P.length( ); // m为模式P的长度
    assert( m > 0); // 若m＝0，退出
    int *next = new int[m]; // 动态存储区开辟整数数组
    assert( next != 0); // 若开辟存储区域失败，退出
    next[0] = -1;
    j = 0; k = -1;
    while (j < m-1) 
    {
        while (k >= 0 && P[k] != P[j])// 不等则采用 KMP 自找首尾子串
            k = next[k]; // k 递归地向前找
        j++; k++; next[j] = k;
    }
    return next;
}

int main()
{
    string s1 = "cocococola";
    string s2 =   "cococola";
    int ret = KMPStrMatching(s1,s2,findNext(s2),0);
    cout << ret <<endl;
    return 0;
}