#10 KMP, Hashing

어떤 문자열 S에서 부분 문자열 t의 존재 여부를 판정하는 문제를 생각해 보자.

가장 단순하게 brute force를 하는 풀이를 우선 떠올릴 수 있다.

모든 s의 index에 대해서, 그 위치에서 시작한 부분 문자열이 t인지를 판정해주면 된다.

s의 길이가 n, t의 길이가 m일때, 시간복잡도가 O(nm)이 걸린다.

 

KMP를 이용하면 동일한 문제를 O(n+m)에 풀 수 있다.

우리가 문자열 2개가 같은 문자열인지를 비교하는 방법을 생각해보자

앞에서 부터 하나씩 살펴보면서 모두 같은면 같은 문자열이다.

우리는 모든 시작점에 대해서 같은 문자열인지 판정해야한다.

문자열 "abaabac"에서 "baab"이라는 문자열이 존재하는지를 확인해보자.

아까도 말했듯이 brute forcing 방법에서는 모든 index에서 검사를 해주어야 한다.

"abaa", "baab", "aaba", "abac" 이 4가지 모든 substring들에 대해서 "baab"와 같은 지를 체크해주자.

 

이제 KMP 알고리즘에 대해 배워보자.

우선 s의 현재 index에서 시작하는 substring이 t와 같은 지를 비교하려면, s의 현재 index 문자와 t의 현재 index의

문자가 같은 지 부터 확인해야 한다.

현재 위치의 문자가 다르다는 사실을 알았으므로 매칭에 실패했다.

생략

 

즉, 비교했던 정보를 통해 t의 어디에서 매칭이 실패 되었는지를 통해, 이 매칭에 실패했을 때, 

뛰어넘을 수 있는 부분이 생긴다.

매칭에 실패했을 때, 어디까지 뛰어넘어야 하는지를 나타내는 함수를 보통 '실패 함수' 라고 한다.

실패 함수는 KMP의 아이디어와 비슷하게 구현할 수 있다.

즉 t에서 t를 매칭하는 방식으로 구현해주자.

 

실패함수의 또 다른 의미는 접두사/접미사의 일치하는 최대 길이로 생각할 수 있다.

현재 보고 있는 접미사에서 최대한 많이 접두사와 겹쳐있을 수록 생갹하기에 유리해지기 때문

fail[x] : 문자열 t의 앞 x번째 index까지 봤을 때 접두사와 접미사의 겹치는 최대 길이

단 문자열 전체가 겹칠 때는 제외한다.

 

Hashing

알파벳만 사용한다고 가정했을 때, 길이 n자리의 문자열의 총 가짓수는 몇가지 일까?

26^n 가지의 문자열이 존재한다.

n이 조금만 커져도 long long 범위를 넘어가는 양의 수많은 문자열이 존재할 수 있다.

그런데 실제 문제에서는 26^n개를 모두 살펴보는 것이 아니기 때문에 적절히 해시함수를 만들어

문자열과 정수 사이 대응을 시킬 수 있다.

hash 함수인 f(x)를 통해 문자열을 정수에 대응 시킬 수 있다.

 

하지만 위의 그림과 같이 맨 위의 문자열 2개가 각각 똑같은 정수에 대응됩니다.

즉, 맨위의 문자열을 s라 하고 그 밑에 있는 문자열을 t라 할때 f(s) = f(t) 라면, 두 문자열 s와 t는 같다고 판정됩니다.

이러한 hash충돌은 필연적으로 일어날 수 밖에 없습니다.

우리는 hash충돌을 최대한 줄이는 방향으로 hash함수를 잡아야 합니다.

따라서 단순히, f(x) = 문자열의 길이 와 같은 단순한 방식으로는 틀리게 됩니다.

 

문자열을 27진수로 표현하자. 즉 a를 1부터 각각 1씩 키우면 대응시켜 z에 27을 대응시키자.

a를 0부터 대응 시키면 f(aa) = f(aaaa) 이므로 1부터 대응시킨다. 

그렇다면 각각의 문자열은 27진수 정수로 표현할 수 있다.

"cda" 같은 경우, 3*27^2 + 4*27^1 + 1*27^0 로 표현할 수 있다.

이렇게 되면 문자열이 1대1로 매칭된다.

하지만 너무 큰 수이기 때문에 보통 modulo(나머지)를 취해줍니다.

또는 같은 hash끼리 벡터에 집어넣어 따로 같은 벡터공간에 있는 hash들을 탐색하면서 문자열을 찾을 수 있습니다.

예시문제

백준 3033 (가장 긴 문자열) c++

이 방법 외에도, suffix array와 lcp를 이용해서 풀 수 있습니다.

해시는 최후의 방법이지, 맹신하면 안됩니다.

다른 문자열 알고리즘으로 풀 수 있다면 해시를 배재하자