[BOJ] 백준 3033 가장 긴 문자열

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

 Input 

11

sabcabcfabc

 

 Output 

3

▶ 문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것 찾기

    (부분 문자열은 일부가 겹쳐서 등장할 수도 있다.)

    (두 번이상이므로 3번 이상 확인할 필요 없이 두 번 등장하였는지만 확인)

    ex) "aaa" → 두 번 이상 등장하는 가장 긴 문자열 "aa"

 

두 번 이상 등장하는 문자열이 있을 때,

→ 첫 번째 문자열은 str[0] ~ str[L-2] 사이에서 시작

→ 두 번째 문자열은 str[1] ~ str[L-1] 사이에서 시작

if) 완전 탐색하는 경우 O(L2)으로 TLE 발생

 

▶ [해시] Hash란?

[해시] Hash란?

 

Parametric Search 이용

두 번 이상 등장하는 부분 문자열 = answer라고 할 때,

answer의 범위는 0 ~ L-1

ex) 문자열 = "abcde" → answer = 0

ex) 문자열 = "aaaaa" → answer = 4

이때, answer = M (≥ 1)인 경우, 1~M개로 이루어진 문자열도 2번 이상 등장할 수 있는것을 확인할 수 있다.

즉, 두 번 이상 등장하는 부분 문자열의 가장 긴 길이가 M일 때 M-1, M-2, ..., 1도 2번 이상 등장합니다.

그저 M이 가장 길이가 클 뿐입니다.

 

ex) 문자열 = "aaaaa" → answer = 4지만 "a", "aa", "aaa"도 2번 이상 등장

low = 0, high = L-1, mid = (low + high) / 2 길이의 문자열 중에

2번 이상 등장하는 가장 긴 길이에 해당하는 최적의 mid를 찾습니다.

이진 탐색(Binary Search)이므로 시간 복잡도 O(L * logL) 발생하므로

2번 이상 발생하는지 확인하는 check()를 O(L) 시간 내에 구현해야 합니다.

 

② mid 길이의 문자열이 2번 이상 나타는지 확인

: Memory Pool + 링크드 리스트 + 문자열 해싱

 

시뮬레이션

① "sabcabcfabc"의 Hash Index = 62998이며, 

    기존에 Hash Table은 비워져 있으므로 [62998] :  sabcabcfabc

 

② 마찬가지로 "abcabcfabc"의 Hash Index = 43430이며

    Hashing 되는 것이 없으므로  → [43430] : abcabcfabc

 

③ [44550] : bcabcfabc

④ [45574] : cabcfabc

⑤ "abcfabc"의 Hash Index = 43430으로 Hashing 과정에서

    htab[43430]에 "abcabcfabc"이 존재합니다.

    길이(mid) =3으로 2번 이상 등장하는 부분 문자열이 있는지 확인합니다.

    ▶abcfabc & abcabcfabc

    

 

Rabin-Karp 알고리즘의 Rolling Hash 기법 이용

길이 M을 Hash Table에 key 값으로 저장할 때, 구간길이 M을 반복해서 처리하는 경우 O(M2) 발생

→ 인덱스 i가 길이 M을 초과하는 경우 구한 Hash 값에서 구간을 벗어난 부분을 제외처리

▶ 'a' × 332 + 'b' ×331 + 'c'

만약 다음 구간길이 M만큼 수치를 구할 때, 'b'와 'c'가 중복되어 있는 것을 확인할 수 있습니다.

즉, 다음 문자로 넘어갈 때, 'a'를 제외하고 'd'를 추가합니다.

('a' × 332 + 'b' ×331 + 'c') × 33 + 'd' - 'a' × 333

이처럼 문자열을 M개씩 연속하여 Hashing할 때, 유용한 기법입니다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

typedef unsigned int UI;
const int LM = 200010;
const int SIZE = 1 << 16;
const int MOD = SIZE - 1;
int N, low, high, mid, ans;
char str[LM];
UI h, wei[LM] = { 1 };
struct Node {
    char* key;
    Node* next;
    Node* alloc(char* nk, Node* np) {
        key = nk, next = np;
        return this;
    }
}buf[LM], * htab[SIZE];
int bcnt;

int strncmp(const char* s, const char* t, int len) {
    int i = 0;
    for (; i < len && s[i] == t[i]; ++i);
    return i == len;
}

void init() {
    bcnt = h = 0;
    for (int i = 0; i < SIZE; i++) htab[i] = NULL;
}

bool check(int mid) {
    // 갱신되는 mid마다 초기화
    init();
    for (int i = 1; i <= N; i++) {
        h = h * 33 + str[i];
        // Rolling Hash 기법
        if (i >= mid) {
            h -= wei[mid] * str[i - mid];
            int hidx = h & MOD;
            Node* p = htab[hidx];
            for (; p; p = p->next) {
                // mid 길이의 부분 문자열이 기존에 등장하였는지 Hash Table에서 확인
                if (strncmp(p->key, &str[i - mid + 1], mid))
                    return true;
            }
            // str + i - mid + 1 == &str[i - mid + 1]
            htab[hidx] = buf[bcnt++].alloc(str + i - mid + 1, htab[hidx]);
        }
    }
    return false;
}

int main() {
    // freopen("input.txt", "r", stdin);
    // Rolling Hash를 편하게 처리하기 위해 인덱스 1번부터
    scanf("%d %s", &N, str + 1);
    for (int i = 1; i <= N; i++) wei[i] = wei[i - 1] * 33;

    high = N - 1; // 최대 N-1 
    while (low <= high) {
        mid = (low + high) / 2;
        if (check(mid)) {
            ans = mid;
            low = mid + 1;
        }
        else
            high = mid - 1;
    }
    printf("%d", ans);
}