[BOJ] 백준 7575 바이러스

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

 Input 

3 4

13

10 8 23 93 21 42 52 22 13 1 2 3 4

11

1 3 8 9 21 42 52 22 13 41 42

10

9 21 42 52 13 22 52 42 12 21

　 

 Output 

YES　

[문제 분석]　

- 감염된 프로그램의 개수 N (2 ≤ N ≤ 100)

- 바이러스 코드 추정을 위한 최소 길이 K (4 ≤ K ≤ 1,000)

- 각 프로그램에 대한 정보

    i 번째 프로그램의 길이를 나타내는 정수 Mi (10 ≤ Mi ≤ 1,000)

    Mi 개의 프로그램 코드를 나타내는 양의 정수 정수의 범위는 1 이상 10,000 이하

 

▶ [해시] Hash란?

[해시] Hash란?

 

[문제 접근]

- 각 프로그램에서 K 이상이 같다면 최소 개수인 K 개가 같은 경우만 고려하면 됩니다.

  (ex. K = 4일때, 최대 길이 5개를 만족한다고 한다면, 이는 길이 4도 만족하기 때문)

- 완전 탐색 방식으로 모두 비교해 볼 경우 시간 복잡도 O(K3) 시간 초과

for(int i=1; i<=an-K+1; ++i)
    for(int j=1; j<=bn-K+1; ++j)
        for(int t=0; t<K; ++t)
            if(A[i+t] != B[j+t]) break;

Rolling Hashing 기법으로 첫번째 "프로그램(수열)"로 K개씩 묶어서 하나의 Hash Table을 생성합니다.

2번째 수열부터 Hash Table에 존재하는지 확인합니다.

존재하는 값에 대해서는 nth번째까지 누적되어야 하므로 nth 값으로 표기합니다.

[예제] K = 4이며, 10진법으로 Hashing 

① 4(=K)개 단위로 위와 같이 7514를 만듭니다.

② 단계 ① 처럼 구하지 않고, 앞에 숫자 『7』에 해당하는 7 × 104 를 빼고, 새로운 숫자 『3』을 더합니다.

    이때 기존 숫자는 10진법이므로 10배 증가합니다. 

    따라서 (① × 10) - (a × 104) + b로 구하면 이러한 과정을 총 {문자열 길이 - K}만큼 수행.

   

   ▶ 새로운 key = (기존 key * base) - (arr[i - K] * w)+ arr[i]

- 첫번째 프로그램(수열)은 기준이 되기 때문에 역순으로 Hash할 필요가 없습니다.

- Test Case가 존재하지 않기 때문에 main문에서 "프로그램(수열)"을 한개씩 비교하면서

  바이러스 추정되는 곳이 없다면 곧바로 "NO"를 출력하고 종료합니다.

  (남은 Input이 있어도 결과에 영향 X)

- 첫번째 수열을 해시해서 O(N - K + 1)에 가능합니다.

  두 번째 수열부터 이전단계에서 일치하는 경우만 확인해서 검사 범위를 줄입니다.

  ex) 3번째 수열에서는 2번째 수열에서 표시된 곳 확인

---

#include <stdio.h>
 
typedef unsigned long long ULL;
const int LM = 1004;
const int MOD = 5381;
const ULL base = 33;
int N, K, pivot[LM], another[LM];
ULL w = 1;
struct Node {
       int nth, * val;
       ULL key;
       Node* next;
       Node* alloc(int* _val, Node* _next, int _nth, ULL _key) {
              val = _val, next = _next, nth = _nth, key = _key;
              return this;
       }
}buf[LM], * htab[MOD];
int bcnt;
 
int comp(int* A, int* B) {
       // ex) "abcd"에서 d의 주소가 전달되었으므로 역으로 비교
       for (int i = 0; i < K; ++i) {
              if (A[-i] != B[-i]) return 0;
       }
       return 1;
}
 
int probing(int* target, int hidx, int cur_nth, ULL key) {
       Node* p = htab[hidx];
       for (; p; p = p->next) {
              // 누적해서 표시된 곳만 확인
              if (p->nth == cur_nth - 1) {
                     // key로 1차 필터, 완전 비교로 2차 필터
                     if (key == p->key && comp(p->val, target)) {
                           // 같은 것이 존재하는 경우 nth 표시
                           p->nth = cur_nth;
                           return 1;
                     }
              }
       }
       return 0;
}
 
int process(int* arr, int len, int nth) {
       int hidx = 0, ret = 0;
       ULL key = 0;
       for (int i = 1; i <= len; ++i) {
              // djb 함수와 유사
              key = key * base + arr[i];
              if (i >= K) { // K 단위 만큼
                     // Rolling Hash
                     key = key - w * arr[i - K];
                     hidx = key % MOD;
                     if (nth == 1) {
                           Node* p = htab[hidx];
                           for (; p; p = p->next) {
                                  if (key == p->key && comp(p->val, arr + i)) {
                                         break;
                                  }
                           }
                           // Hash Table에 존재하지 않는 경우 (중복 제거)
                           if (!p) htab[hidx] = buf[bcnt++].alloc(arr + i,  htab[hidx], nth, key);
                     }
                     else {
                           ret += probing(arr + i, hidx, nth, key);
                     }
              }
       }
       // 누적해서 바이러스로 추정되는 것이 1개 이상인 경우
       return ret > 0;
}
 
void reverse(int* num, int y) {
       for (int x = 1; x < y; ++x, --y) {
              int temp = num[x];
              num[x] = num[y];
              num[y] = temp;
       }
}
 
int main() {
       // freopen("input.txt", "r", stdin);
       int i, j, len, ret;
       scanf("%d %d", &N, &K);
       // Rolling Hash를 편하게 하기 위한 변수 설정
       for (i = 1; i <= K; ++i) w = w * base;
       // 첫번째 프로그램(수열)로 Hash Table 완성
       scanf("%d", &len);
       for (i = 1; i <= len; ++i) scanf("%d", pivot + i);
       process(pivot, len, 1);
       for (i = 2; i <= N; ++i) {
              scanf("%d", &len);
              ret = 0;
              for (j = 1; j <= len; ++j) scanf("%d", another + j);
              
              // 정방향 검사
              ret = process(another, len, i);
              // 역방향 검사
              reverse(another, len);
              ret += process(another, len, i);
              // 어느 방향으로도 존재하지 않는 경우
              if (ret == 0) {
                     puts("NO");
                     return 0;
              }
       }
       puts("YES");
}