백준 7575번 : 바이러스 - KMP

https://www.acmicpc.net/problem/7575

7575번: 바이러스

#include <bits/stdc++.h>

using namespace std;

vector<int> getFail(const vector<int> &pattern) {
    int n = pattern.size();
    vector<int> fail(n);
    int j = 0;
    for (int i = 1; i < n; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            fail[i] = ++j;
        }
    }
    return fail;
}

bool KMP(const vector<int> &pattern, const vector<int> &text) {
    vector<int> fail = getFail(pattern);
    int n = text.size();

    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (text[i] == pattern[j]) {
            if (j == pattern.size() - 1) {
                return true;
            } else {
                j++;
            }
        }
    }

    return false;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> code[n];
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        vector<int> v(m);
        for (int j = 0; j < m; j++) {
            cin >> v[j];
        }
        code[i] = v;
    }

    // pattern
    for (int i = 0; i < code[0].size() - k + 1; i++) {
        vector<int> pattern(k);
        for (int j = 0; j < k; j++) {
            pattern[j] = code[0][i + j];
        }

        vector<bool> check(n);
        for (int j = 1; j < n; j++) {
            check[j] = KMP(pattern, code[j]);
        }

        // reverse
        for (int j = 1; j < n; j++) {
            if (check[j]) continue;
            reverse(code[j].begin(), code[j].end());
            check[j] = KMP(pattern, code[j]);
        }

        bool ans = true;

        for (int j = 1; j < n; j++) {
            if (!check[j]) {
                ans = false;
                break;
            }
        }

        if (ans) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";

    return 0;
}