7575 바이러스

Link

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

Detail

단순 KMP 문제다. 다만 벡터의 복사를 최적화 하기위해서 함수의 오버로드와 iterator를 적극적으로 사용하였다.

Code

#include <bits/stdc++.h>
#define MOD 10007
#define MAX 1'000'000
 
using namespace std;
typedef long long ll;
 
typedef vector<int> program;
typedef program::iterator pIter;
typedef program::reverse_iterator rpIter;
 
// O(n)
bool contains_virus(
    pIter start,
    pIter end,
    pIter sub_start,
    pIter sub_end,
    const vector<int>& pi
    ) {
    // use kmp
 
    int j = 0;
    for (int i = 0; i < end - start; i++) {
        while (j > 0 && start[i] != sub_start[j]) {
            j = pi[j - 1];
        }
 
        if (start[i] == sub_start[j]) {
            if (j == sub_end - sub_start - 1) {
                return true;
            }
            j++;
        }
    }
 
    return false;
}
 
bool contains_virus (
    rpIter start,
    rpIter end,
    pIter sub_start,
    pIter sub_end,
    const vector<int>& pi
    ) {
    // use kmp. reversed
 
    int j = 0;
    for (int i = 0; i < end - start; i++) {
        while (j > 0 && start[i] != sub_start[j]) {
            j = pi[j - 1];
        }
 
        if (start[i] == sub_start[j]) {
            if (j == sub_end - sub_start - 1) {
                return true;
            }
            j++;
        }
    }
 
    return false;
}
 
// O(n)
vector<int> getPi(pIter begin, pIter end) {
    vector<int> pi(end - begin, 0);
 
    int j = 0;
    for (int i = 1; i < end - begin; i++) {
        while (j > 0 && begin[i] != begin[j]) {
            j = pi[j - 1];
        }
 
        if (begin[i] == begin[j]) {
            pi[i] = ++j;
        }
    }
 
    return pi;
}
 
int main() {
    int program_cnt, min_virus;
    int program_size;
    cin >> program_cnt >> min_virus;
 
    vector<program> programs(program_cnt);
    for (int i = 0; i < program_cnt; i++) {
        cin >> program_size;
        programs[i].resize(program_size);
        for (int j = 0; j < program_size; j++) {
            cin >> programs[i][j];
        }
    }
 
    pIter sub_start;
    pIter sub_end;
 
    // O(M - K + 1) * O(N) * O(M + K) = O(N * M * K)
    for(int i = 0; i < programs[0].size() - min_virus + 1; i++) {
        sub_start = programs[0].begin() + i;
        sub_end = programs[0].begin() + i + min_virus;
 
        // build pi
        vector<int> pi = getPi(sub_start, sub_end);
        bool contains = true;
 
        for (int j = 1; j < program_cnt; j++) {
            // 각 프로그램이 reverse포함해서 kmp 성립되는지 확인
            bool success =
                contains_virus(
                programs[j].begin(), 
                programs[j].end(), 
                sub_start, 
                sub_end, 
                pi) 
                or
                contains_virus(
                programs[j].rbegin(), 
                programs[j].rend(), 
                sub_start, 
                sub_end, 
                pi);
 
            if (!success) {
                // cout << "failed at " << j << endl;
                contains = false;
                break;
            }
        }
        
        if (contains) {
            cout << "YES" << endl;
            return 0;
        }
 
    }
 
    cout << "NO" << endl;
}