KMP算法模板

KMP算法模板

原理

见参考文章

模板

#include <iostream>
#include <cstring>
#define max_n 100005
using namespace std;
char s[max_n] = {'a','a','b','a','a','a','b','c'};
char p[max_n] = {'a','a','a','b'};
int nxt[max_n];//nxt跳转表，nxt[k]表示在k之前有的最大相同前后缀的长度
void get_next(char* p,int nxt[])//构造nxt表
{
    int pLen=strlen(p);
    nxt[0] = -1;//nxt表首元素必为-1，表示没元素会和他配对，要重新开始匹配模式串
    int k = -1;//初始为-1，重新开始的标志也是-1
    int j = 0;
    while(j<pLen-1)
    {
        //p[j]是后缀,p[k]是前缀
        if(k=-1||p[j]==p[k])//如果重新匹配或者成功匹配
        {
            ++j;
            ++k;
            if(p[j]!=p[k])
            {
                nxt[j] = k;
            }
            else nxt[j] = nxt[k];//避免p[j]==p[nxt[j]],所以继续递归，k=nxt[k]=nxt[nxt[k]]
        }
        else
        {
            k = nxt[k];
        }

    }
}
int KMP(char* s,char* p)
{
    int i = 0;//原串
    int j = 0;//模式串
    int sLen = strlen(s);
    int pLen = strlen(p);
    while(i<sLen&&j<pLen)
    {
        if(j==-1||s[i]==p[j])//若匹配或者j==-1
        {
            ++i;
            ++j;
        }
        else//若失配且j!=-1
        {
            j = nxt[j];
        }
    }
    if(j==pLen)
    {
        return i-j;//返回成功匹配的第一个开始位置，此时j=pLen
    }
    else
    {
        return -1;//未找到匹配字串
    }
}
int main()
{
    get_next(p,nxt);
    for(int i = 0;i<4;i++)
    {
        cout << nxt[i] << " ";
    }
    cout << endl;
    cout << KMP(s,p) << endl;
    return 0;
}

参考文章

v_JULY_v，从头到尾彻底理解KMP（2014年8月22日版），https://blog.csdn.net/v_july_v/article/details/7041827 （一篇通透）