[알고리즘] 백준 7575 cpp

우선 문제를 풀기 위해서는 다음과 같은 과정이 필요하다.

1. 비교 바이러스 코드를 추출할 프로그램 선정
   모든 프로그램이 바이러스 코드를 가지고 있기 때문에 한 프로그램을 골라서 비교 코드를 추출하면 된다. 그리고 추출한 비교 코드를 나머지 프로그램들이 가지고 있는지 확인하면 된다. 편의상 프로그램 1번에서 비교 코드를 추출하고 나머지 프로그램들과 비교하기로 한다.

2. 비교 코드는 길이 K만큼 추출
   조건 때문에 비교 코드는 최소 길이가 K이다. 그리고 비교 코드를 추출하면 뒤집힌 코드도 같이 생성한다. 문제에서 뒤집힌 형태로 코드가 일치하는 경우도 있다고 했기 때문이다.

3. 비교 방식 선택
   빠른 비교를 위해서 원래는 KMP를 많이 쓰는 모양이다. 하지만 나는 보이어-무어의 Bad Character Shift를 사용했다.

보이어-무어 Bad Character Shift 설명 (이전 포스팅)

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX_NUM_LEN 10001

// 테이블을 생성
void makeBadNumTable(vector<int> & target, int length, int * table) {
    int i;

    for(i = 0; i < MAX_NUM_LEN; i++)
        table[i] = -1;
    for(i = 0; i < length; i++)
        table[target[i]] = i;
}

// target을 base에서 검색
// 찾으면 바로 종료
bool search(vector<int> & target, vector<int> & base, int * table) {
    int len_base = base.size();
    int len_target = target.size();

    int s = 0, j;
    while(s + len_target <= len_base) {
        j = len_target - 1;

        while(j >= 0 && (target[j] == base[j + s]))
            j--;

        if(j >= 0) {
            s += max(1, j - table[base[s + j]]);
        }
        else {
            return true;
        }
    }
    return false;
}

int main() {
    int N, K, M, temp;
    cin >> N >> K;

    vector<vector<int>> programs(N);

    for(int i = 0; i < N; i++) {
        cin >> M;

        for(int j = 0; j < M; j++) {
            cin >> temp;
            programs[i].emplace_back(temp);
        }
    }

    // programs[0] . target 생성
    // programs[1~]  base

    int length = programs[0].size() - K + 1, s = 0;

    while(s < length) {
        vector<int> target(K);
        vector<int> rev_target(K);

        // 타켓 생성
        for(int i = 0; i < K; i++) {
            target[i] = programs[0][i + s]; // target
            rev_target[K - i - 1] = programs[0][i + s]; // reverse target
        }

        // 테이블 생성
        int table[MAX_NUM_LEN]; // BadNumTable
        makeBadNumTable(target, K, table);
        int rev_table[MAX_NUM_LEN]; // reverse_BadNumTable
        makeBadNumTable(rev_target, K, rev_table);

        int count = 1;
        for(int i = 1; i < N; i++) 
            if(search(target, programs[i], table) || search(rev_target, programs[i], rev_table))
                count++;

        if(count == N) {
            cout << "YES";
            return 0;
        }
        s++;
    }   
    cout << "NO";
}