KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）.

KMP算法的关键是根据给定的模式串W1,m,定义一个next函数,next函数包含了模式串本身局部匹配的信息.

#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;

void BuildPatchMatchTable(int *partMatchTable, char *findstr)
{
    if(findstr == NULL)
        return;
    partMatchTable[0] = 0;
    int sizefind = strlen(findstr);
    for(int i = 1; i < sizefind; ++i)
    {
        set<string> preset;
        string tmppre = "";
        tmppre = findstr[0];
        preset.insert(tmppre);
        for(int j = 1; j < i; ++j)
        {
            tmppre = tmppre + findstr[j];
            preset.insert(tmppre);
        }

        set<string> postset;
        string tmppost = "";
        tmppost = findstr[i];
        postset.insert(tmppost);
        for(int j = i - 1; j > 0; --j)
        {
            tmppost =  findstr[j] + tmppost;
            postset.insert(tmppost);
        }
        set<string> comset;
        for(set<string>::iterator beg = preset.begin(); beg != preset.end(); ++beg)
        {
            if(postset.count(*beg) > 0)
                comset.insert(*beg);
        }
        int maxlen = 0;
        for(set<string>::iterator beg = comset.begin(); beg != comset.end(); ++beg)
        {
            if((*beg).size() > maxlen)
                maxlen = (*beg).size();
        }
        partMatchTable[i] = maxlen;
    }
}

int kmp(char *srcstr, char *findstr)
{
    if(srcstr == NULL || findstr == NULL)
        return -1;
    int lensrc = http://www.mamicode.com/strlen(srcstr);>

C++ KMP 算法