KMP C++ 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> makePI(const string& pattern) {
    int m = pattern.size();
    vector<int> PI(m, 0);
    int k = 0;

    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern[k] != pattern[i])
            k = PI[k - 1];
        if (pattern[k] == pattern[i])
            k++;
        PI[i] = k;
    }

    return PI;
}

void KMP(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> PI = makePI(pattern);
    int k = 0;

    // 디버깅을 위한 출력
    cout << "텍스트: " << text << endl;
    cout << "패턴: " << pattern << endl;
    cout << "PI 배열: ";
    for (int val : PI) {
        cout << val << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        while (k > 0 && pattern[k] != text[i])
            k = PI[k - 1];
        if (pattern[k] == text[i])
            k++;
        if (k == m) {
            cout << "매칭 위치: " << i - m + 1 << endl;
            k = PI[k - 1];
        }
    }
}

int main() {
    string text, pattern;

    getline(cin, text);
    getline(cin, pattern);

    KMP(text, pattern);

    return 0;
}