[BOJ] 백준 10840 구간성분

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

 Input 

afcdrdesdefwszr

gedsrddemzr

　 

 Output 

7

문자열로 구성된 두 서열에서 같은 성분을 가진 구간 중에서

가장 긴 구간을 찾아 그 구간의 길이를 출력하는 문제

 

▶ [해시] Hash란?

[해시] Hash란?

 

구성 성분이 같은 최대 길이를 구하는 것이므로 

큰 값부터 작은 값까지 줄여가며 구성성분을 확인 하는 경우에는 TLE 발생

※ 구성 성분이 같은지 확인하는 방법은 26개의 알파벳 크기를 이용해서

    cnt[1 ... 26] 배열을 이용할 수 있습니다. ex) cnt[1] = 3 = "a"가 3번 등장

 

이분 탐색으로 길이 K를 찾는 방법의 경우도 적용하기 쉽지 않습니다.

"abcd"와 "bdac"가 있을 때, 길이 1은 구성이 같습니다.

하지만 길이 2, 3에는 구성성분이 같은 것이 없지만 길이 4에는 구성성분이 같습니다.

즉, 이분탐색의 경우에는 길이 K가 만족할 때, K 미만의 해도 만족해야 하지만

그렇지 않은 Case가 있기 때문에 이분 탐색 의미가 없습니다.

 

결과적으로 최대값 K에서 1씩 줄여가며 순차탐색으로 만족하는 K를 찾아야 합니다.

※ 주어지는 두 문자열의 길이가 다를 수 있기 때문에 길이 K의 최대값 = min(SA 크기, SB 크기)

Hash를 이용해서 같은 구성성분이 있는지 확인할 수 있습니다.

a ~ z까지 26개의 알파벳을 djb2 해시를 고려해서 가중치 테이블을 활용합니다.

3326 값은 unsigned long long 범위로도 담을 수 없지만 어차피 64bit만 남기에

충분히 unique하기 때문에 크게 신경쓰지 않습니다.

 

빠른 Hashing 처리를 위해서 Rolling Hashing 처리합니다.

key값으로 먼저 검사하지만 동일한 성분인지 확인할 때, 

"abcd"에서 끝지점 "d"의 주소가 전달 되기 때문에 역순으로 2차 검사 합니다.

---

#include <stdio.h>
 
typedef unsigned long long ULL;
inline int min(int A, int B) { return A < B ? A : B; }
const int LM = 1504;
const int MOD = 5381;
int ans, aLen, bLen, A[LM], B[LM];
ULL weight[30] = { 1 };
char str[LM];
struct Node {
       int* addr;
       ULL key;
       Node* next;
       Node* alloc(int* _addr, Node* _next, ULL _key) {
              addr = _addr, next = _next, key = _key;
              return this;
       }
}buf[LM], *htab[MOD];
int bcnt;
 
void init() {
       for (int i = 0; i < MOD; ++i) htab[i] = NULL;
       bcnt = 0;
}
 
void input(int *arr, int &len) {
       scanf("%s", str);
       // 문자열 길이를 저장
       // 포인터를 이용해서 각 원소를 배열에 저장
       for (; str[len]; ++len) arr[len + 1] = str[len] - 'a';
}
 
int comp(int *ap, int *bp) {
       int cnt[26] = { 0 };
       // 구간의 끝지점 주소가 변수 ap, bp로 넘어오기에 역순 검사
       for (int i = 0; i < ans; ++i) {
              cnt[ap[-i]]++;
              cnt[bp[-i]]--;
       }
       // 26개 알파벳이 모두 0이어야 동일한 성분
       for (int i = 0; i < 26; ++i)
              if (cnt[i]) return 0;
       return 1;
}
 
int probing(int* bp, ULL key, int hidx) {
       Node* p = htab[hidx];
       for (; p ; p = p->next) {
              // key값이 같을 때, 구성성분이 같은지 확인
              if (key == p->key && comp(p->addr, bp)) {
                     return 1;
              }
       }
       return 0;
}
 
void process() {
       // ans 크기를 1씩 줄여가면 확인
       for (ans = min(aLen, bLen); ans > 0; --ans) {
              // 달라지는 길이 ans에 따라 Hash Table 재구성
              init();
              
              // 첫번째 문자열을 토대로 Hash Table을 만듭니다.
              ULL key = 0;
              for (int i = 1; i <= aLen; ++i) {
                     key += weight[A[i]];
                     // Rolling Hashing 처리
                     if (i > ans) key -= weight[A[i - ans]];
                     if (i >= ans) {
                           int hidx = key % MOD;
                           // Hash Table에서 중복값이 많지 않을 것이기에 중복처리 X
                           htab[hidx] = buf[bcnt++].alloc(A + i, htab[hidx],  key);
                     }
              }
              key = 0;
              for (int i = 1; i <= bLen; ++i) {
                     key += weight[B[i]];
                     if (i > ans) key -= weight[B[i - ans]];
                     // i가 현재 추정 길이(ans)가 되었을 때,
                     // Hash Table에서 동일한 성분이 있는지 확인
                     if (i >= ans && probing(B + i, key, key % MOD))
                           return;
              }
       }
}
 
int main() {
       // freopen("input.txt", "r", stdin);
       // Hash를 위한 가중치 변수
       for (int i = 1; i < 26; ++i) weight[i] = weight[i - 1] * 33;
       
       input(A, aLen); input(B, bLen);
       process();
       printf("%d\n", ans);
}