안녕하세요. rdd6584입니다.

문자열이라면 절레절레 하던 제가 이번 네블컵을 준비하면서, 해시에 대해 어느정도 이해를 하게 되었습니다. 그래서 해시로 여러가지 장난을 쳐봤고, 해시로 풀 수 있는 문제와 기법을 소개해보려고 합니다.

일단, 해시함수로는 롤링해시 함수인 라빈카프 알고리즘을 사용합니다. 따라서 라빈카프 알고리즘이 선행되어야 합니다.

https://www.acmicpc.net/problem/1605 반복 부분문자열

공통 문자열이 등장하는 횟수는 단조감소하므로, 이분탐색 + 라빈카프를 작성하면 됩니다.

https://www.acmicpc.net/problem/6206 Milk Patterns

이 문제를 볼까요? 앞 문제는 2번 이상, 이 문제는 K번 이상인 문자열이라는 점이 다릅니다. 하지만 라빈카프를 그대로 사용하는 것은 문제가 있습니다. 해시충돌이 날 경우, O(N)짜리 단순 비교를 통해서 탐색을 하게 되는데 N == K인 경우, 길이 N짜리 문자열을 K번 단순비교 해야 하므로 시간적으로 문제가 되겠지요. 그러면 차라리 '해시값이 같을 경우 같은 문자열이다'라고 생각하는 것은 어떨까요? 일반적으로 10억개의 버켓에서 20만개의 원소를 담는 것은 70%정도의 확률로 충돌이 일어난다고 합니다. 너무 크네요. 그런데 만약에 그러한 버켓이 10억개 더 있다고 해봅시다. 만약에 10억개의 버켓에서 충돌이 일어났던 원소 쌍을 또 다시 다른 버켓 10억개로 옮겨담는다고 치면, 여기서마저 그 쌍들이 겹칠 확률은 얼마나 될까요? 정확히는 모르겠습니다만, 처음 10억개 담아서 충돌이 일어났던 쌍의 개수가 많지 않을테고, 그러한 쌍이 또 다음 10억개에서 충돌이 일어날 확률은 상당히 작다는 것을 알 수 있습니다. 충돌이 거의 불가능하다고 생각하시면 됩니다. 만약에 조금 불안하면 10억개의 버켓을 또 가져오면 되겠지요. 이런식으로 서로 다른 모듈로로 인해 계산된 해시값을 직렬로 연결해서 사용하는 것을 한번 반복할 때 마다 확률이 극한으로 떨어지는 것을 알 수 있습니다.

그러면 위 6206문제로 돌아가서 다시 풀어봅시다. 말씀 드렸다시피, 서로 다른 모듈로로 구해진 해시값을 직렬로 연결해서 서로 다른 원소의 충돌확률을 극한으로 떨어뜨립시다. 만약 해시값이 같을 경우 같은 문자열이라고 가정하고 문제를 해결하시면 됩니다. 직렬 모듈로 처리는map<pair<int, int>, int>나 Trie 같은 알고리즘을 사용하시면 됩니다. map같은 경우, 직렬 개수를 더 확장시키기 위해서는 구조체를 정의해서 사용하면 되겠네요.

https://www.acmicpc.net/problem/3033 가장 긴 문자열

이 문제를 풀어봅시다. 1605번과 완전히 동일한 문제지만 시간이 1초로 적습니다. 저 같은 경우는 계속해서 시간초과가 났는데요. 어떻게 해결할 수 있을까요? 해시값을 구하는 것은 매번 O(1)이므로, 사실상 시간의 영향은 MAP으로 같은 값을 탐색하는 과정이 지배합니다. 이 시간을 조금 줄여볼 수는 없을까요? 가장 간단한 방법은, MAP이 힘들지 않게 나눠서 저장하는 것 입니다.

map[333][333]; // 이런 식으로 선언해서,
map[HASH[0] %333][HASH[1] % 333][HASH] = 1; // 대충 이런 식으로 짜면 되겠네요.

이러면 MAP이 병렬로 분산되기 때문에 걸리는 부하를 줄여서 시간을 절약할 수 있고 이 차이는 꽤 큽니다.

만약에, T[i] : S[i...] 의 prefix들 중 S의 prefix이기도 한 녀석들 중 길이가 가장 긴 녀석의 길이를 구하고 싶습니다. 어떻게 하면 될까요? 이는 흔히 Z-Algorithm으로 구할 수 있다는 것이 알려져 있습니다. 하지만, 해싱으로도 위 문제를 빠르게 해결할 수 있습니다.

1. Hash[i] = p^(n - 1) * s[1] + p^(n - 2) * s[2] + ... + p^(n - i) * s[i]로 정의해서 O(N)에 배열을 채웁니다. (라빈카프 finger print와 동일한 함수입니다.)

2. 어떤 i에 대해서, 길이 x만큼의 문자열이 공통 prefix인지 확인해봅시다. 즉, S[1 ~ x]와 T[i ~ i+x-1]가 같은 지 확인하려고 합니다. 그러면 식을 정리해봅시다. { Hash[x] == (Hash[n-i+x] - Hash[n-i]) * p^(n-i) }인지 판단해서 같다면, S[1 ~ x]와 T[i ~ i+x-1]는 같습니다.

3. 모든 i = (1, 2, 3, ..., n)에 대해서 이분탐색으로 최대 x를 결정해주면, 우리가 구하고자 했던 가장 긴 prefix의 길이를 구할 수 있습니다. O(NlogN) 비록, Z알고리즘보다는 느리지만 아는 것을 활용하는 것은 좋으니까요.

위 아이디어로 해결할 수 있는 문제입니다.

https://www.acmicpc.net/problem/13713 문자열과 쿼리

https://www.acmicpc.net/problem/1786 찾기

문자열 탐색 알고리즘도 마찬가지로 해시로 해결할 수 있습니다. 찾고자 하는 문자열의 해시값을 저장해두고, 원본 문자열에서 라빈카프를 진행해주면 됩니다.

https://www.acmicpc.net/problem/16160 이진 트리와 수열

네블컵에 나왔던 문제이면서 해싱으로 풀 수 있는 문제입니다.

감사합니다.

권일우