KMP算法模板

KMP算法模板，使用C++完成。

#include 

using namespace std;

const int MAXN = 1000;
const int MAXM = 100000;

int nextTable[MAXM]; // nextTable[i] 表示pattern[0:i-1]的公共前后缀长度
int pattern[MAXM];
int text[MAXN];

void getNextTable(int m)
{
    int i = 0, j = -1; // j 指向pattern[0:i]的公共前后缀的前缀末尾
    nextTable[i] = -1; // 初始化next[0]，代表如果第一个字符就失配，则直接加一（即右移）即可
    while(i < m){
        if(j == -1 || pattern[i] == pattern[j]){ // 如果匹配，则向右扩展一位
            i++;
            j++;
            nextTable[i] = j;
        }
        else{ // 不匹配，回退j继续判断
            j = nextTable[j];
        }
    }
    return;
}

int kmp(int n, int m)
{
    getNextTable(m);
    int i = 0;
    int j = 0;
    while(i < n && j < m){
        if(j == -1 || text[i] == pattern[j]){ // 如果匹配，直接右移继续比较
            i++;
            j++;
        }
        else{ // 不匹配
            j = nextTable[j];
        }
    }
    if(j == m){
        return i - j + 1; // 匹配成功，返回
    }
    else{
        return -1;
    }
}