KMP算法代码模板

被这个破算法搞晕了，只能硬背下来了:(

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

//2021-3-19 10:06

const int MAXM = 1000;

int nextTable[MAXM];

void GetNextTable(string A) {
    int j = 0;
    nextTable[j] = -1;
    int i = nextTable[j];
    while (j < A.size()) {        //求nextTable[j],所以j不回溯，匹配失败时i回溯
        if (i == -1 || A[j] == A[i]) {
            i++;
            j++;
            nextTable[j] = i;        //更新nextTable
        } else {
            i = nextTable[i];        //i回溯
        }
    }
    return;
}

bool KMP(string str, string P) {
    GetNextTable(P);
    int i = 0;
    int j = 0;
    while (i < str.size() && j < P.size()) {        //匹配时，i指向主串，i不会回溯，j指向模式串，匹配失败时j会回溯
        if (j == -1 || str[i] == P[j]) {
            i++;
            j++;
        } else {
            j = nextTable[j];        //j回溯
        }
    }
    if (j == P.size()) {
        return true;
    } else {
        return false;
    }
}

int main() {
    string str, pattern;
    while (cin >> str >> pattern) {
        if (KMP(str, pattern)) {
            printf("Match\n");
        } else {
            printf("No match\n");
        }
    }
    return 0;
}