KMP字符串匹配算法

KMP字符串匹配算法可以理解为一种经过优化的暴力匹配。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using int_t = long long int;

int_t nxt[1000000 + 1];

void getNext(string pattern) {
    nxt[0] = -1;
    int_t k = -1;
    int_t j = 0;
    while (j < pattern.length()) {
        if (k == -1 || pattern[j] == pattern[k]) {
            if (pattern[++j] == pattern[++k]) {
                nxt[j] = nxt[k];
            } else {
                nxt[j] = k;
            }
        } else {
            k = nxt[k];
        }
    }
}

int main() {
    srand(time(0));
    string pattern, source;
    memset(nxt, 0, sizeof (nxt));
    int_t x1, x2;
    cin >> x1>>x2;
    for (int_t i = 0; i < x1; i++) {
        source = source + char(rand() % 5 + 'A');
    }
    for (int_t i = 0; i < x2; i++) {
        pattern = pattern + char(rand() % 5 + 'A');
    }
    cout << source << endl << pattern << endl;
    int_t i = 0, j = 0;
    getNext(pattern);
    while (i < source.length() && j < (signed long long) pattern.length()) {
        //cout << "x:i=" << i << " j=" << j << endl;
        if (j == -1 || source[i] == pattern[j]) {
            //cout << "i=" << i << " j=" << j << " ok" << endl;
            i++;
            j++;
        } else {
            //  cout << "j=" << j << " to " << nxt[j] << endl;
            j = nxt[j];
        }
        if (j == pattern.length()) {
            cout << i - j + 1 << endl;
            i = i - j + 2;
            j = 0;
        }
        // cout << "y:i=" << i << " j=" << j << endl;
        ///  cout << (i < source.length()) << " " << (j < (signed long long )pattern.length()) << endl;
    }
    for (int_t i = 0; i < pattern.length(); i++) cout << nxt[i] << " ";
    cout << endl;
    main();
    return 0;
}