Baekjoon 7575번 바이러스

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n, k, Mi;
string s;
vector<string> M[100];

vector<int> getPi(int start, int end, bool reverse){
    vector<int> pi(k, 0);
    int j = 0;
    for(int i = 1; i < k; i++){
        if(!reverse){
            while(j > 0 && M[0][i+start] != M[0][j+start])
                j = pi[j-1];
            if(M[0][i+start] == M[0][j+start]){
                j += 1;
                pi[i] = j;
            }
        }
        else{
            while(j > 0 && M[0][end-i-1] != M[0][end-j-1])
                j = pi[j-1];
            if(M[0][end-i-1] == M[0][end-j-1]){
                j += 1;
                pi[i] = j;
            }
        }
    }
    return pi;
}

vector<int> kmp(int idx, int start, int end, bool reverse, vector<int>& pi){
    vector<int> ans;
    int j = 0;
    for(int i = 0; i < M[idx].size(); i++){
        if(!reverse){
            while(j > 0 && M[idx][i] != M[0][j+start])
                j = pi[j-1];
            if(M[idx][i] == M[0][j+start]){
                if(j == k-1){
                    ans.push_back(i-k+1);
                    j = pi[j];
                }
                else{
                    j += 1;
                }
            }
        }
        else{
            while(j > 0 && M[idx][i] != M[0][end-j-1])
                j = pi[j-1];
            if(M[idx][i] == M[0][end-j-1]){
                if(j == k-1){
                    ans.push_back(i-k+1);
                    j = pi[j];
                }
                else{
                    j += 1;
                }
            }
        }
    }
    return ans;
}

void solve(){
    for(int i = 0; i <= M[0].size()-k; i++){
        bool detect = true;
        auto pi = getPi(i, i+k, false);
        auto rpi = getPi(i, i+k, true);
        for(int j = 1; j < n; j++){
            if(kmp(j, i, i+k, false, pi).size()) continue;
            if(kmp(j, i, i+k, true, rpi).size()) continue;
            detect = false;
            break;
        }
        if(detect){
            cout << "YES";
            exit(0);
        }
    }
    cout << "NO";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> Mi;
        for(int j = 0; j < Mi; j++){
            cin >> s;
            M[i].push_back(s);
        }
    }
    solve();
    return 0;
}

처음 제출한 코드는 기준으로 하는 문자열 끝에 위치한 길이가 k인 패턴을 시도해보지 않아서 틀렸습니다가 출력되었다. (범위 코딩 실수)

두번째에 ac를 받았는데 무언가 좀 이상했다. kmp 알고리즘에서 pi 배열을 만드는 함수를 엉망으로 작성했는데도 틀렸습니다가 출력되지 않았기 때문이다. 원인은 패턴의 개수를 찾는것이 아닌 등장 여부를 확인하기 위해 kmp 알고리즘을 사용했기 때문이였다. pi 배열이 올바르게 만들어지지 않았어도 처음 등장한 패턴은 문제없이 찾아낼 수 있다.