10840 구간성분

문자열 A, B가 주어지고 두 문자열에서 동일한 substring중에서 가장 긴 것의 길이를 구하는 문제다.

문제 해결전략

1. 롤링 해시 사용

2. 최대 길이를 검사하는 것이므로 길이가 긴 것에 대해서 먼저 검사하고 찾으면 바로 리턴해버린다.

3. 이런 문제의 경우 동일한 길이를 두번 검사하지 않으므로 check배열을 bool보다는 int로 짜서 해당 해시값이 표현하는 문자열의 길이를 저장한다면 check 배열 초기화가 필요가 없다. 여러 탐색문제에서 check배열을 bool로 표현하지 않고 int로 해서 test_case값이나 다른 값으로 표시하는 것과 같은 이치다.

풀이

문자열 A, B의 최대 길이가 1500이므로 길이별로 모두 조사를 하게 되면

A에서 n개의 문자열과 B에서 n개의 문자열을 단순비교하면

for(n = min(len(A),len(B)); n > 0; n--) {
    for(i = 0; i < len(A) - n; i++) {
        for(j = 0; j < len(B) - n; j++) {
            for(k = 0; k < n; k++)
                if(A[i + k] != B[j + k]) break;
            if(k == n) return n;
        }
    }
}    // time complexity =~ O(n^4)

이런 식으로 체크하는데 n은 최대 1500이므로 n^4는 당연히 시간초과가 날 것이다.

만약 해시를 사용해서 비교를 하면

int check[mod]
// time complexity = len
hashing(char *s, int start_pos, int len)
    return hashed_value
for(n = min(len(A),len(B)); n > 0; n--) {
    check[] = {0,}
    for(i = 0; i < len(A) - n; i++) {
        hash_a = hashing(A, i, n)
        check[hash_a] = 1
    }
    for(j = 0; j < len(B) - n; j++) {
        hash_b = hashing(B, j, n)
        if(check[hash_b])
            return n
    }
}    // time complexity =~ O(n^3)

와 같이 되어서 n^4이 n^3으로 줄어든다. 여기서 추가로 살펴볼 점은 해싱의 처리방식이다. 해시함수를 하나 예로 들자면

hashing(char *s, int start_pos, int len) {
    for(i = 0; i < len; i++)
        ret = (ret*w + s[start_pos + i]) % mod;
    return ret;
}    // time complexity = len

이런 방식으로 처리한다. 여기서 리턴되는 ret값에서 mod를 떼고 생각해 보면

ret[p] = s[p]*w^(len-1) + s[p+1]*w^(len-2) + s[p+2]*w^(len-3) + ... s[p+len-2]*w + s[p+len-1]

이고 다음 위치에서의 해시값은

ret[p + 1] = s[p+1]*w^(len-1) + s[p+2]*w^(len-2) + s[p+3]*w^(len-3) + ... + s[p+len-1]*w + s[p+len]

가 된다. ret[p]에 w를 곱하고 ret[p+1]와 비교를 하면

ret[p]*w = s[p]*w^(len) + s[p+1]*w^(len-1) + s[p+2]*w^(len-2) + ... + s[p+len-2]*w^2 + s[p+len-1]*w

ret[p + 1] =                   s[p+1]*w^(len-1) + s[p+2]*w^(len-2) + ... + s[p+len-2]*w^2 + s[p+len-1]*w + s[p+len]

가 된다. 이제 두 식을 연립하면

ret[p+1] = ret[p]*w - s[p]*w^(len) + s[p+len]

이 된다. 우리는 기존 해시함수로는 길이 len인 문자열을 해싱할 때 O(len)이 들었지만 위 식을 이용하면 O(1)에 해결 할 수 있다.

이걸 롤링 해시라고 부른다더라.

int check[mod]
 
hashing(char *s, int start_pos, int len)
    return hashed_value
 
rolling_hash(hash, char *s, int start_pos, int len)
    return rolled_hash
 
for(n = min(len(A),len(B)); n > 0; n--) { 
    check[] = {0, }
    hash_a = hashing(A, 0, n)
    check[hash_a] = 1
    for(i = 1; i < len(A) - n; i++) {
        hash_a = rolling_hash(hash_a, A, i, n)
        check[hash_a] = 1
    }
    
    hash_b = hashing(B, 0, n)
    if(check[hash_b]) 
        return n
    for(i = 1; i < len(B) - n; i++) {
        hash_b = rolling_hash(hash_b, B, i, n)
        if(check[hash_b]) 
            return n
    }
}    // time complexity =~ O(n^2)

대략 이렇게 된다. 진짜 딱 이렇게 짜면 바로 틀렸습니다가 뜰 것이다.

왜냐하면 해시 충돌(hash collision)이 일어나기 때문인데 해시를 처리하는 방식에 따라서 문자열이 달라도 같은 해시값을 가지게 될 수 있기 때문이다.

아무리 w, mod값을 큰 소수로 사용한다 해도 운이 더럽게 나쁘면 충돌이 일어나기 마련이고 심지어 우리는 메모리의 한계 때문에 mod값을 제한받는다.

해시 충돌을 해결하는 방법은 여러가지가 있는데 내가 이 문제에서 사용한 방식은 다중 해시다. 정확히는 3중 해시를 사용했다.

한 문자열에 대해 다른 방식으로 연산한 해시값 3개를 가지고 이 3개가 모두 같아야 같은 문자열이라고 인식하는 방식이다.

이건 그냥 기도메타다. 2중 해시로 기도했을 때는 실패했었다. 다중 해시는 테케가 많아질 수록 틀릴 확률이 높아진다.

만약 테케가 추가된다면 이 코드로는 WA가 뜰 것이고 그때는 chaining을 사용한 코드를 짜서 추가하겠다.

해싱 팁 

1. 다중 해시보다는 chaining을 추천한다.

2. 어차피 chaining할 거 *연산보다 <<연산을 사용하는게 더 빠르다.

3. 문자열 길이가 해당 문제처럼 짧다면 곱하거나 <<하는 것보다 특정한 문자에 특정한 값을 부여하고 그냥 더하는 방식(아래 코드에서 사용하는 방식)이 더 빠르다. 어차피 해싱이라는거 자체가 어떤 데이터를 다른 유니크한 데이터로 치환(표현)하는 것이므로 목적만 이룰 수 있다면 빠른게 좋지 않을까. 만약 문자열이 매우 길다면 단순히 더하는 것만으로는 해시 충돌이 어마어마하게 일어나서 더 느려질 수도 있으므로 적절하게 사용해야 한다.

4. 계산 과정에서 int범위를 넘어갈 수도 있으므로 계산 과정을 잘 살펴봐야 한다.

5. 보통 해시는 문자열을 처리할 때 많이 사용하는데 문자열을 잘못 처리하면 제대로 된 해시값을 얻지 못할 수 있다. 예를들어 소문자만 들어오는 경우 s[i] - 'a'만 하면 hash(aaaaaa) == hash(a) == 0이 되어버린다. s[i]를 그대로 갖다쓰는게 편하다. 처리해야할 데이터가 숫자라면 0000 같은 입력을 조심해야 한다.

※ 주의할점 : 이 팁은 해싱 관련 문제를 풀다가 느낀 점을 정리한 것으로 실제로 사용할 때에도 적용가능한지는 확실하지 않다.

<코드>

#include <stdio.h>
#define mod1 822539
#define mod2 556211
#define mod3 75401
 
#pragma warning(disable:4996)
 
typedef long long ll;
 
int sl, pl, check1[mod1], check2[mod2], check3[mod3];
int pr[26] = { 71, 83, 131, 163, 191, 307, 317, 337, 353, 383, 401, 431, 457, 479, 503, 523, 547, 569, 587, 601, 613, 683, 719, 739, 751, 787 };
int m[3][26];
char s[1502], p[1502];
 
int strlen(char* s) {
    int i = 0;
    while (s[i] != 0 && s[i] != '\n')i++;
    return i;
}
 
int init_hash(char *str, int len, int cas) {
    ll mod = cas == 2 ? mod3 : cas == 1 ? mod2 : mod1;
    ll temp = 0;
    for (int i = 0; i < len; i++) {
        temp += m[cas][str[i] - 'a'];
        temp %= mod;
    }
    return (int)temp;
}
 
int next_hash(int hash, int cas, int start, int len, char* str) {
    int mod = cas == 2 ? mod3 : cas == 1 ? mod2 : mod1;
    return (hash - m[cas][str[start - 1] - 'a'] + m[cas][str[start + len - 1] - 'a'] + mod) % mod;
}
 
int rolling_hash(int sl, int pl, char* str1, char* str2) {
    char *sh = str1, *lo = str2;
    if (pl < sl) {
        sh = str2; lo = str1;
        sl = sl^pl; pl = pl^sl; sl = sl^pl;
    }
    int hs[3], hl[3], _hash[3];
    for (int i = 0; i < 3; i++) {
        hs[i] = init_hash(sh, sl, i);
        hl[i] = init_hash(lo, sl, i);
    }
    
    for (int i = 0; i < sl; i++) {
        for (int j = 0; j < 3; j++)
            _hash[j] = hs[j];
        check1[_hash[0]] = check2[_hash[1]] = check3[_hash[2]] = sl - i;
        for (int j = 1; j <= i; j++) {
            for (int k = 0; k < 3;k++)
                _hash[k] = next_hash(_hash[k], k, j, sl - i, sh);
            check1[_hash[0]] = check2[_hash[1]] = check3[_hash[2]] = sl - i;
        }
        for (int j = 0; j < 3; j++)
            _hash[j] = hl[j];
        if (check1[_hash[0]] == sl - i && check2[_hash[1]] == sl - i && check3[_hash[2]] == sl - i)
            return sl - i;
        for (int j = 1; j <= pl - sl + i; j++) {
            for (int k = 0; k < 3; k++)
                _hash[k] = next_hash(_hash[k], k, j, sl - i, lo);
            if (check1[_hash[0]] == sl - i && check2[_hash[1]] == sl - i && check3[_hash[2]] == sl - i)
                return sl - i;
        }
        for (int j = 0; j < 3; j++) {
            int mod = j == 2 ? mod3 : j == 1 ? mod2 : mod1;
            hs[j] = (hs[j] - m[j][sh[sl - i - 1] - 'a'] + mod) % mod;
            hl[j] = (hl[j] - m[j][lo[sl - i - 1] - 'a'] + mod) % mod;
        }
    }
    return 0;
}
 
void init() {
    ll temp1 = 1, temp2 = 1, temp3 = 1;
    for (int i = 0; i < 26; i++) {
        temp1 *= pr[25 - i];
        temp2 *= pr[25 - i];
        temp3 *= pr[25 - i];
        temp1 %= mod1;
        temp2 %= mod2;
        temp3 %= mod3;
        m[0][25 - i] = (int)temp1%mod1;
        m[1][25 - i] = (int)temp2%mod2;
        m[2][25 - i] = (int)temp3%mod3;
    }
}
 
int main() {
    init();
    scanf(" %s %s", s, p);
    sl = strlen(s);
    pl = strlen(p);
    bool cmp = sl > pl;
    printf("%d\n", rolling_hash(sl, pl, s, p));
}