백준 7575번: 바이러스 (C++)

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

7575번: 바이러스

---

Solved By: KMP

 

길이가 K이상인 코드가 반복되어 나타난다면 바이러스라 판단하므로 길이가 K인 코드가 반복되어 나타나도 바이러스라고 판단할 수 있습니다.

 

N개의 코드 중, 첫 번째 코드( == code[0])를 비교 코드로 두고, code[0]에서 길이가 K인 코드들을 구합니다.

-> compareCode

 

그리고, 나머지 코드들 (code[1] ~ code[N - 1])에 code[0]에서 구한 길이가 K인 코드들이 속하는지 봅니다.

물론, code[1] ~ code[N - 1]을 reverse시킨 것도 확인해야 합니다.

 

확인하는 과정에서 O(K * 2(N - 1))의 시간 복잡도, O(K * N)이 발생합니다. 데이터의 개수를 보았을 때, 시간 초과 문제가 없을 거 같지만 시간을 단축시키기 위해 KMP를 활용하여 O(K + 2(N - 1)), O(K + N)으로 줄여줍시다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 101
using namespace std;

int n, k;
vector<int> code[MAX];

vector<int> getPi(vector<int> p){
    vector<int> pi(p.size(), 0);
    
    for(int i = 1, j = 0; i < p.size(); i++){
        while(j > 0 && p[i] != p[j]) j = pi[j - 1];
        if(p[i] == p[j]) pi[i] = ++j;
    }
    
    return pi;
}

bool kmp(vector<int> s, vector<int> p){
    vector<int> pi = getPi(p);
    
    for(int i = 0, j = 0; i < s.size(); i++){
        while(j > 0 && s[i] != p[j]) j = pi[j - 1];
        if(s[i] == p[j]){
            if(j == p.size() - 1){
                return 1;
            }
            else{
                j++;
            }
        }
    }
    return 0;
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int l; cin >> l;
        for(int j = 0; j < l; j++){
            int v; cin >> v;
            code[i].push_back(v);
        }
    }
    
    bool flag = 0;
    
    // code[0]의 부분 순열(size == k)들을 비교 값으로 둔다.
    for(int i = 0; i < code[0].size(); i++){
        vector<int> compareCode(k);
        for(int j = 0; j < k; j++){
            compareCode[j] = code[0][i + j];
        }
        
        // compareCode를 기준으로 탐색
        // code[1] ~ code[N - 1] 혹은 reverse 시킨 것들에 존재하는지 확인
        bool flag2 = 1;
        for(int j = 1; j < n; j++){
            vector<int> revCode = code[j];
            reverse(revCode.begin(), revCode.end());
            // 시간 단축을 위해 KMP 사용
            if(!kmp(code[j], compareCode) && !kmp(revCode, compareCode)){
                flag2 = 0;
            }
        }
        
        // 모든 code에서 compareCode와 하나라도 일치하는 것이 있다면 됨.
        if(flag2) flag = 1;
    }
    
    if(flag) cout << "YES";
    else cout << "NO";
    
    return 0;
}