[실전 알고리즘] 0x0E강 - 문자열(KMP, 라빈 카프)_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x1E강 - KMP에서 확인할 수 있습니다. 리뉴얼한 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

반갑습니다, 이번 시간에는 문자열 알고리즘을 공부해보겠습니다. 미리 주의사항을 좀 알려드리자면, 특히 KMP의 경우 정말 헷갈립니다. 저도 이번 강의 자료를 만들면서 엄청 애를 먹었습니다. 그렇기 때문에 이 강의를 보고 알듯말듯한 정도만 되어도 성공일 것입니다. 그리고 어차피 문자열 관련 알고리즘은 코딩테스트에 정말 드문 빈도로 나오는 알고리즘들이고, 이 강의를 건너뛰어도 다른 강의를 듣는 것에 지장이 없으므로 이해가 잘 안가면 다음으로 미뤄두셔도 됩니다.

 

 

2017 카카오 신입 공채 코딩테스트와 2018 카카오 공채 코딩테스트를 보시면 문자열을 가지고 장난질을 쳐야하는 문제가 군데군데 있음을 알 수 있습니다. C언어에서 char*를 가지고 문자열을 다루는 것에 비해 C++에서는 그럭저럭 편해졌긴 하지만, 여전히 Python에 비해서는 문자열을 다루기 정말 불편합니다. 그렇기 때문에 지금 코드에서 일부 method를 알려드리긴 하지만, 시간 복잡도를 크게 고려할 필요가 없는 상황에서 문자열을 빡세게 다뤄야하는 문제라면 Python을 쓰시는 것을 강력하게 추천드립니다.

 

이번 강의에서 사용할 용어들을 몇 가지 정의하고 가겠습니다. 첫 번째로 문자열의 slicing은 Python에서 많이 사용하는 것인데 본문에서 설명을 할 때도 저 표기가 간단해서 많이 사용했습니다. 혹시 Python을 이전에 배운 적 없어 S[a:b]를 처음 보면 저기 적혀있는 정의를 잘 숙지해주세요.

 

접두사와 접미사는 각각 문자열의 첫 문자를 포함하는 연속한 문자열, 문자열의 끝 문자를 포함하는 연속한 문자열을 의미합니다.

 

"문자열 문제가 어려워봤자 얼마나 어렵겠어? 그냥 적당히 싸바싸바하면 되지" 라고 생각할 수 있으나 현실은 그렇지 않습니다.. 바로 이런 류의 문제를 해결하기 위해 저희는 문자열 알고리즘을 공부를 하는 것입니다.

 

첫 번째로 다룰 알고리즘은 KMP 알고리즘입니다. KMP 알고리즘은 문자열 A 안에 문자열 B가 들어있는지를 판단하는 알고리즘입니다. 일단 알고리즘을 배우지 않은 상황에서 A 안에 B가 있는지를 확인하려면 어떻게 해야할까요?

 

A의 앞부분이 B와 일치하는지 확인하는데 맨 첫글자부터 틀리네요.

 

A의 2번째 글자부터 확인했는데 또 틀리네요.

 

 

 

 

 

 

 

 

A 안에서 B를 찾았습니다. 뭐 이런식으로 구현을 하겠죠?

 

대부분의 언어에서 패턴 매칭 문제를 해결하는 메소드는 이런식으로 구현이 되어있을 것입니다. 이 구현의 시간복잡도는 최악의 경우 얼마일까요?

 

지금 이 예시가 최악의 예시입니다.

 

끝까지 가고 나서야 틀렸음을 알게되고

 

한 칸 옮겨서도 마찬가지고

 

끝날때까지 쭉 그렇죠.

 

즉 최악의 경우 $O(|A| \times |B|)$입니다. $|A|$는 A의 길이를 의미합니다.

 

KMP 알고리즘은 패턴 매칭 문제를 $O(|A| \times |B|)$가 아닌 $O(|A| + |B|)$에 해결할 수 있게 해주는 기적의 알고리즘입니다. 그리고 제 입장에서는 진짜 뒤돌아설 때 마다 헷갈려요.. 이번에 강의 자료 만들면서도 엄청 고생했어요.

 

아무튼 KMP 알고리즘을 이해할 때, KMP에서 쓰이는 "실패함수"를 알면 KMP를 이해하는데 도움이 됩니다.

 

실패함수 F(x)는 S[0:k] = S[x+1-k:x+1]을 만족하는 최대 k입니다. 단 k는 x 이하여야 합니다. 최대한 간결한 정의를 써보려고 했는데, 아무리 노력해도 그게 안되더라구요.. 저 정의대신 밑의 그림을 보시면 이해가 조금 쉬울 것 같습니다.

 

F(2)를 구하려면 S의 앞 3글자인 "ABA"에서 앞 k글자와 뒤 k글자가 일치하는 최대의 k를 구하면 됩니다. 이 때 k = 3이면 그냥 글자 전체이니 의미가 없어서 k는 2 이하라는 제한을 둔 것입니다. k = 2일 때는 앞 2글자는 "AB"이고 뒤 2글자는 "BA"이기 때문에 k는 2가 아닙니다. k = 1일 때는 각각 "A"와 "A"이므로 F(2) = 1입니다.

 

마찬가지로 F(3)을 구하기 위해서는 "ABAB"를 살펴봐야하고, 여기서 앞 3글자는 "ABA"인 반면 뒤 3글자는 "BAB"이기에 k는 3이 아닙니다. k = 2일 때는 앞 2글자와 뒷 2글자 모두 "AB", "AB"이기에 k = 2입니다.

 

주어진 그림에서 초록색 윗줄과 하늘색 밑줄의 내용이 같게 하고싶은 상황이라고 이해하시면 됩니다.  

 

그러면 이 실패함수를 어떻게 구하는걸까요? 사실 아직 실패함수가 왜 필요한지조차 제대로 다루지 않았지만 그건 천천히 이해하는 것으로 합시다.

 

예를 들어 F(6)을 구하고 싶으면 k = 5, 4, 3, 2, 1을 차례로 해보면 됩니다.

 

 

 

 

 

 

이 때 전체 F를 구하는 시간복잡도는 $O(|S|^3)$입니다. 그런데, 전체 F를 무려 $O(|S|)$에 구하는 방법이 있습니다. 전혀 감이 안오시겠지만 같이 알아봅시다.

 

일단 F[3] = 2임은 미리 구해뒀다 치고 F[4]를 구해봅시다. 그림의 상황을 보면 알겠지만, F[4]를 구할 때 S[2]와 S[4]가 "A"로 같음으로 인해 k = F[3]+1일 때 앞 k글자와 뒤 k글자가 일치함을 알 수 있습니다. 일단 F[4] >= F[3]+1임은 자명하네요. 그런데 이 둘이 같다는 것은 어떻게 보일 수 있을까요?

 

만약 F[4]가 F[3]+1보다 크다고 해봅시다. 그러면 k' = F[4]-1 > F[3]에 대해, S[0:4] = "ABAB"의 관점에서 앞 k'글자와 뒷 k'글자가 같아야함을 의미합니다. 그리고 이는 F[3]의 정의와 모순입니다. 지금 이 설명이 이해가 안간다면 일단 넘어가고 한 다섯 슬라이드 뒤에 나올 그림을 보면서 이해하면 될 것 같습니다.

 

그 다음으로 F[5]를 구해보겠습니다. 이번에는 S[3]과 S[5]가 "B"와 "C"로 다르기 때문에 F[5]를 F[4]+1로 구할 수 없습니다. 이제 어떻게 해야할까요?

 

저희가 S[3]과 S[5]을 비교한 것, 즉 F[5]가 4인지 확인한 것은 곧 S[2]부터 시작한 문자열이 S[0]부터 시작한 문자열과 일치하는지 확인하는 것입니다.

 

그런데 F[5]가 4가 아님을 알았으니 시작점을 S[2]보다 오른쪽으로 옮겨야하는데, 어디로 옮겨야할까요?

 

일단 저희는 F[3] = 1인 것은 알고 있다고 합시다. 이 말은 곧 S[0:2] != S[3:5]임을 의미합니다.

 

시작점은 S[2]에서 오른쪽으로 가야하는데, 만약 시작점이 S[3]이려면 적어도 S[0:2] = S[3:5]이어야 합니다. 그런데 F[3] = 1인 것으로부터 S[0:2] != S[3:5]임을 알기 때문에 애초에 S[2]와 S[5]를 비교할 필요도 없이 시작점이 S[3]일 수 없음을 알 수 있습니다.

 

이러한 원리로 시작점을 뛰어넘으면서 실패함수를 빠르게 구할 수 있게 되고, 구체적인 예시와 함께 이해해봅시다.

 

일단 F[0] = 0으로 둡니다.

 

이후 i와 j는 각각 1, 0에서 시작을 합니다. 우리는 S[i]와 S[j]를 비교하면서 실패함수의 값을 구하고자 합니다. 밑의 문자열은 관념적으로만 존재하고, 계속 오른쪽으로 이동합니다. 실제 구현에서는 j의 값에 따라 자연스럽게 문자열이 오른쪽으로 이동하는 것과 같은 효과를 줍니다.

 

일단 S[1]과 S[0]이 다르므로 F[1]은 0입니다. 

 

시작점이 S[1]일 때 불일치가 발생했으니 시작점을 옮겨야겠죠. j를 그대로 두면 자연스럽게 시작점이 한 칸 오른쪽으로 옮겨진 것과 동일합니다. 이번에는 S[0]과 S[2]가 동일하므로 F[2] = 1입니다.

 

시작점을 더 오른쪽으로 가면 손해이니 일치할 때 까지 계속 갑니다.

 

 

지금이 문제입니다. S[3]과 S[5]가 일치하지 않아서 시작점을 옮겨야하는데, 어디로 옮겨야할까요? 아까 했던 논의를 생각해보면 시작점을 S[2]에서 S[4]로 옮겨야함을 알 수 있습니다.

 

시작점을 S[4]로 옮긴다는 것은 S[1]와 S[5]를 비교해야한다는 뜻이고, 잘 생각해보면 불일치가 발생할 때 j = F[j-1]로 옮기면 됨을 알 수 있습니다. 이 부분이 정말 헷갈리는데 설명을 잘 하려고 해도 한계가 있네요ㅠㅠ 다른 분들의 자료를 참고해서 이해해보시면 좋을 것 같습니다.

 

S[1]과 S[5]도 일치하지 않았고, 또 시작점을 밀어야 합니다.

 

j를 0으로 옮겼고 S[0]과 S[5]가 다르므로 F[5] = 0입니다. 시작점을 한 칸 오른쪽으로 옮깁니다.

 

다시 일치가 되므로 시작점이 고정된 채로 계속 진행합니다. 시작점이 고정된다는 의미는 i, j가 동일하게 1씩 더해짐을 의미합니다.

 

 

이렇게 F를 구하는 과정이 종료되었습니다.

 

결국 매번 비교가 일어날 때 마다 i가 1 증가하거나 밑의 문자열이 최소 1칸은 오른쪽으로 이동하므로 시간복잡도는 $O(|S|)$입니다. 이 과정을 코드로 옮기면 이렇게 간단합니다. 깊이 사유해서 깨닫는데 성공하시면 좋겠습니다!

 

이렇게 우여곡절끝에 찾고싶은 패턴 B에 대한 실패함수를 찾아내는데 성공했습니다. 신기하게도 이를 이용해 A에서 B를 찾는 과정이 실패 함수를 찾는 과정과 굉장히 유사합니다. 같이 해봅시다.

 

또 다시 i, j가 나옵니다. 일단 처음엔 일치하네요.

 

계속 갑시다.

 

 

 

 

중요한 부분은 여기입니다. 이렇게 불일치가 발생했을 때 어디로 옮겨야할까요? 옮기는 위치와 F[4] 사이의 연관성을 알겠나요? F[4]에서는 "ABABA"에서 앞 k글자와 뒷 k글자가 일치하는 최대 k = 3을 저장하고 있습니다. 잘 생각해보면 한 칸 옮기는 것은 의미가 없습니다. 만약 한 칸 옮겨서 매칭이 잘 되려면 "ABAB"와 "BABA"가 같았어야, 즉 F[4] = 4여야 했겠죠.

 

두 칸을 옮긴다는 의미는 곧 3개, 즉 F[4]개의 글자는 이미 일치함을 알 수 있습니다. 이 점으로부터 생각해보면 왜 j를 F[4]의 값으로 바꾸면 되는지를 알 수 있습니다.

 

 

똑같은 상황이네요.

 

마찬가지로 j를 F[4](=3)으로 변경합니다.

 

 

 

 

 

 

 

 

j는 8이 되는 순간 매칭이 완료됨을 알 수 있습니다. 그런데 저희는 단순히 A 안에 B가 들어있는지 여부만을 알고싶은 것이 아니라, B가 들어있는 모든 위치를 찾고 싶습니다. 시작점을 어디로 옮겨야할까요? F[8]과 관계가 있음을 알겠나요?

 

j를 F[8]로 바꿉니다.

 

중략해서 i = 20, j = 8로 이동했습니다. 마찬가지로 또 등장하는 위치를 찾았네요. 다시 j를 F[8]로 바꿉시다.

 

사실 이 때 이미 밑의 문자열이 바깥으로 벗어났기 때문에 더 이상은 불가능함을 알 수 있지만, 실패함수를 사용하는 법을 이해하는데 도움이 될 것 같아 계속 진행해보겠습니다. S[3]과 S[21]이 불일치할 때 j를 어떻게 옮겨야할까요?

 

정답은 j = F[2]입니다. 앞의 한 글자는 일치하도록 시작점을 옮기는 상황인거죠.

 

또 불일치가 발생하니 j = F[0] = 0이 됩니다. 이후 i가 증가되면서 범위를 벗어나게 되어 KMP가 종료됩니다.

 

BOJ 1786번 : 찾기 문제를 해결하는 코드를 확인해보세요. 이 KMP 알고리즘에서의 실패함수를 응용해 해결할 수 있는 다양한 문제들이 있지만 난이도가 저세상이라 굳이 언급은 안하겠습니다. 지적 유희를 즐기고 싶다 하시면 강의글 마지막에 있는 링크들에서 응용 문제들을 확인해보세요.

 

길고 긴 KMP가 끝났습니다. 개인적으로는 라빈 카프가 KMP보다 쉽던데, 여러분이 느끼기에도 그러면 좋겠습니다. 라빈 카프는 문자열에서 쓸 수 있는 해쉬 함수로, 적절한 전처리를 통해 부분문자열의 해쉬 값을 바로 알 수 있다는 장점이 있지만 잘 써먹으려면 많은 정수론 지식이 필요합니다. 수학 올림피아드를 준비했다거나, 수학과이거나 해서 정수론을 이전에 깊게 공부한적이 있으면 어렵지 않게 이해할 수 있을텐데 그런게 아니라면 그냥 이해를 포기하고 성질만 가져다 쓴다고 생각하시면 좋을 것 같습니다.

 

굉장히 기네요. 일단 합동식은 0x0B강 - 수학에서 다룬 적이 있으니 다시 설명하지는 않겠습니다. 첫 번째로 곱셈에 대한 역수를 알아봅시다. mod $m$에 대해 곱이 1인 두 수는 서로 역수관계에 있습니다. 예를 들어 2*3 = 1(mod 5)이므로 2는 3의 곱셈에 대한 역수입니다. 물론 3은 2의 곱셈에 대한 역수이기도 합니다.

 

두 번째 내용은 페르마의 소정리라고 불리는 정리로서, 소수 $p$와 1이상 $p-1$ 이하의 임의의 정수 $a$에 대해 $a^ \equiv 1 (mod p)$입니다. 그리고 이 정리에 따라 mod $p$에서 1이상 $p-1$ 이하의 임의의 정수 $a$에 대해 $a^{-1}$($a$의 역수)는 $a^$입니다.

 

세 번째로 원시근이라는 무시무시한 용어가 나오는데요, $a^0, a^1, \dots a^$를 $p$로 나눈 나머지가 모두 다르다면 $a$를 $p$의 원시근이라고 합니다. 추상적이라 골치아프면 적어놓은 예시들을 잘 살펴보세요.

 

왜 뜬금없이 빡센 정수론 공부를 하고 있냐면, 라빈 카프 알고리즘에서 쓰이기 때문입니다. 라빈 카프 알고리즘을 돌릴 때 적당히 큰 소수 $p$와 $p$에 대한 원시근 $a$가 필요합니다. $p$가 소수가 아니어도, $a$가 $p$에 대한 원시근이 아니어도 알고리즘 자체는 잘 동작하지만 해쉬 충돌이 많이 발생할 수 있습니다. 만약 string을 전 슬라이드에서 한 것과 같이 해쉬테이블에 넣고 싶으면 $p$를 대략 100만~500만 정도의 소수로 잡으면 됩니다. 그런데 다음 슬라이드에서와 같이 문자열이 같은지를 판단하는 목적으로 쓰기 위해서라면 $p$를 int 범위 내에서 최대한 큰 소수로 잡아주는 것이 좋습니다.

 

라빈 카프 알고리즘에서 해쉬 값은 마치 문자열을 $a$ 진법으로 나타낸 것과 동일한 상황입니다. 예를 들어 321을 $3 \times 10^2 + 2 \times 10^1 + 1 \times 10^0$이라고 쓰듯, 문자열 "xyz"에 대한 해쉬 값을 $x \times a^2 + y \times a^1 + z \times a^0$으로 나타내는 것입니다. 이 때 $x, y, z$와 같은 문자열의 값은 아스키코드로 표현을 하면 됩니다. 단, 이렇게 되면 문자열의 길이가 길어짐에 따라 수가 굉장히 커지게 되므로 적절한 소수 $p$에 대해 $p$로 나눈 나머지로 관리를 하는 것입니다.

 

두 문자열 A, B의 해쉬 값이 같다면 이 둘은 $1-1/p$의 확률로 동일한 문자열입니다. $p$가 크면 클수록 길이가 같을 때 그냥 해쉬 값만 같으면 두 문자열이 동일하다고 취급해도 됨을 알 수 있습니다. 직접 예시를 확인해보세요.

 

앞에서 KMP 알고리즘으로 풀었던 BOJ 1786번 : 찾기 문제를 라빈 카프 알고리즘으로 풀어보겠습니다. 푸는 과정은 일단 P의 해쉬 값을 구하고, T에서 모든 길이 4짜리 부분문자열의 해쉬 값을 구하면서 P의 해쉬 값과 일치하는지를 확인하면 됩니다.

 

원칙적으로는 적당히 큰 소수 $p$와 $p$에 대한 원시근 $a$가 필요한데, 그냥 지금은 서술의 편의를 위해 $a = 5, p = 509$로 두겠습니다. 일단 P의 해쉬 값은 쉽게 계산할 수 있습니다.

 

T의 앞 4글자, 즉 T[0:4]에 대한 해쉬값도 계산을 해봅시다.

 

T[1:5]에 대한 계산식도 적어보았습니다. 크게 어려움이 없을 것입니다.

 

그런데 저희는 T[0:4]를 이용해 T[1:5]를 빠르게 계산하고 싶습니다. 지금은 $O(|T|)$가 걸리는데 $O(1)$에 말이죠. 식을 잘 보면 이런식으로 한 개의 항을 빼면 겹치는 부분이 많음을 알 수 있습니다.

 

식을 잘 변형하면 $O(1)$에 계산이 가능합니다. 식이 낯설게 느껴지면 "23456789"에서 $3456 = 2345\times10 - 2\times10^4 + 6\times10^0$이라는 점을 곰곰히 생각해보시면 도움이 될 것입니다.

 

비슷한 방식으로 쭉쭉 계산하면 됩니다.

 

 

 

 

 

 

 

방식이 잘 이해가시나요? 아마 의문점이 생기신 분이 많을 것입니다. 해쉬 값만 같다고 해서 실제 문자열이 같다는 보장을 할 수 있을까 하는 의문점을 짚어보겠습니다. 당연히 해쉬 값만 같다고 해서 실제 문자열이 같다는 보장은 할 수가 없습니다. 그렇기에 100% 정확한 답을 내려면 실제로 두 문자열이 동일한지를 비교하는 루틴이 추가되어야 하나, 그렇게 되면 이 문제에서 P가 50만개의 A이고 T가 100만개의 A일 때 총 $500000^2$번의 비교가 필요해 시간초과가 발생합니다. 그러므로 틀릴 가능성을 감수하고라도 두 문자열이 같은지 비교하지 않습니다.

 

하지만 안심하셔도 되는 점은, $p$가 $10^9$정도의 소수일 경우 답이 틀리지 않을 확률은 아무리 낮게 잡아도 99.90% 정도입니다. 단, $a$가 작으면 충돌쌍이 의도치않게 쉽게 찾아질 수 있습니다. 예를 들어 $a = 2$일 때 "AC"와 "BA"의 해쉬 값은 동일합니다.

 

또한 $a$가 $p$의 원시근이 아닐 경우에도 적혀있는 예시와 같이 충돌쌍이 쉽게 찾아질 수 있습니다. 그렇기에 일단 소수 $p$를 정하고 $a$를 원시근으로 두어야하는데, 사실 원시근을 빠르게 구할 방법이 없습니다. 그러니 미리 울프람알파같은 곳에서 원시근을 정해두고 $a, p$를 외워가거나 그냥 운에 맡기셔야 합니다. $a = 302, p = 1000000007$인 라빈 카프 코드를 확인해보세요.

 

사실 라빈 카프는 더 무궁무진한 활용법이 있습니다. 지금은 길이가 $k$로 고정된 부분문자열의 해쉬값들만 $O(|S|)$에 구할 수 있는데, 사실 $O(|S|)$의 전처리를 거치고 나면 임의의 $x, y$에 대해 $S[x:y]$의 해쉬 값을 $O(1)$에 구할 수 있게 됩니다.

 

바로 Prefix Sum 기법을 활용하는 것인데요, Prefix Sum 기법은 0x09강 - 다이나믹 프로그래밍 24p에서 간단하게 언급한 바가 있습니다. 일단 Psum 테이블을 채워보겠습니다.

 

 

 

 

Psum 테이블에 어떤 값이 들어가는지는 이해하셨죠?

 

이제 $S[x:y]$의 해쉬 값은 $a^{-(|S|-y)}(Psum[y]-Psum[x])$로 계산이 가능합니다. 우리는 $a^{-1} = a^$임을 알고 있고 $a^$는 재귀적으로 $O(log p)$에 구할 수 있음을 알 수 있습니다.

 

처음으로 슬라이드 100장에 도달했네요,,, 이번 강의에서는 KMP, 라빈 카프에 대해 배웠습니다. 만약 코딩테스트의 문자열 문제에서 단순 패턴 매칭 문제를 넘어선 무언가가 나온다면 그냥 손절하시는걸 추천드립니다. 일부러 그룹 문제집에도 응용 문제는 하나도 넣어놓지 않았습니다. 그룹에 있는 1764번 : 듣보잡, 7785번 : 회사에 있는 사람의 경우, 사실 STL set이나 map을 사용하면 해결이 가능하지만 B형을 대비하신다면 STL set, map 대신 라빈 카프를 포함한 해쉬 테이블로 해결을 해보시는 연습을 해보시는 것을 추천드립니다.

 

그리고 더 공부하고 싶으신 분들을 위해 개인적으로 도움이 많이 됐던 글 몇 개의 링크를 남겨놓고 이만 강의를 마치겠습니다. 라빈 카프의 응용 - rdd6584님, KMP의 설명과 응용 - kks227님, KMP 설명과 응용2 - bowbowbow님