[문자열] 맨버 마이어스 알고리즘

문자열 알고리즘에서 유용하게 쓰이는 suffix array. 사전순으로 정렬된 suffix array를 구하기만 한다면, 그로부터 LCP를 구하여 중복 부분문자열을 쉽게 구할 수 있다. 하지만 접미사들을 사전순으로 정렬하여 suffix array로 만드는 그 시간이, 문자열이 길어질수록 끔찍하게 길어진다.

길이 n자리의 문자열들을 사전순으로 정렬하려면 자리수마다 sort하여 총 n번의 sort가 필요한데, 이걸 길이가 수만 수십만인 문자열에 적용할 수 있을 리가 없다. 때문에 접미사의 특징을 이용하여 n번의 sort 대신, logn번의 sort만으로 사전순 정렬이 가능하게 할 필요가 있다.

 

맨버 마이어스 알고리즘을 한줄로 요약하면 아래와 같다.

'접미사의 정렬에 한해서는 n번의 sort를 하지 않고, 0, 1, 2, 4, 8...번째만 정렬해도 제대로 정렬된다' (물론 적절한 전처리는 해야한다.)

사전순으로 정렬하려면 당연히 모든 자리수를 다 sort해야 할텐데, 어째서 2의 배수가 아닌 자리는 건너뛰는가.

그것은 접미사는 자기보다 길이가 긴 접미사에 포함되기 때문이다.

예를 들어 abcd의 접미사 abcd, bcd, cd, d를 보면, cd는 bcd, abcd에 포함된다. 다시 말하면, 길이 4인 접미사 abcd의 2번째 자리 c는, 길이 2인 접미사 cd의 0번째 자리와 같다.

그리고 2^n 이하의 모든 자연수는 2^n-1 이하의 2의 제곱의 합으로 표현된다.

이 두 성질이 맞물려 3, 5, 6, 7...번째를 직접 정렬하지 않아도 되는 것이다.

 

예를 들어 길이 4 이상의 접미사 abcdefgh와 efgh가 있어 둘을 3번째 인덱스(d, h)의 비교로 정렬해야 한다고 하자.

abcd...와 efgh의 3번째인 d와 h는, 길이 3 이상의 접미사 bcdefgh와 fgh의 2번째이다.

그리고 3번째 인덱스로 정렬하는 이 시점에, bcd랑 fgh를 2번째 인덱스대로 정렬한 결과는 이미 갖고 있을 것이다.

그렇기 때문에 abcd와 efgh를 3번째 자리대로 정렬하지 않아도, bcd랑 fgh를 2번째 자리대로 정렬했을때의 결과를 불러오면 정렬이 가능하다.

일반화하면, i번째 인덱스대로 정렬하려고 할때 i = 2^k + p 라면, i번째를 직접 정렬해보지 않아도 i보다 길이가 2^k만큼 짧은 접미사의 p번째 정렬 결과가 이미 있으므로 그것을 불러오는 것이다.

이와 같은 방법으로, i가 2^(k+1)이하일 때에는 이전의 결과만으로 정렬이 가능하다.

그리고 i = 2^(k+1)이 되었을 때 기존의 결과만으로는 정렬이 불가능하므로 다시 한번 2^(k+1)번째 자리수에 대해 정렬을 시행한다.

예를 들어 15번째 인덱스대로 정렬하려면 15 = 8 + 7이므로, 그보다 길이가 8만큼 짧은 접미사의 7번째 인덱스대로 정렬한 결과를 불러오면 된다. 하지만 16번째 인덱스대로 정렬하려면 16 = 8+ 8인데, 길이가 8만큼 짧은 접미사의 8번째 인덱스(=9번째 문자)의 정렬 결과는 아직 없고, 그러므로 16번째 인덱스에 대해 직접 sort를 해야한다.

이를 반복하면 0, 1, 2, 4, 8...번째의 정렬만으로도 사전순으로 정렬된 suffix array를 구할 수 있다.

 

원리는 이러한데, 위에서 '이전 결과를 불러온다'고 쉽게 말한 부분이 실제로 구현하기에 머리가 아프다.

그냥 자리수마다 n번 sort할 때에는 문자를 내장함수 ord()에 넣어서 코드값을 비교하면 끝이지만, 맨버 마이어스 알고리즘을 쓸 경우 매 정렬마다 rank라는 문자열간의 우선순위를 결정하는 리스트를 새로 만들어 새로 정의한 함수가 그 rank값을 비교해서 정렬해야 한다.

실제로 구현한 코드를 보기 전까지는 도저히 이해가 안되던데 9249의 풀이를 써보면서 정리해야겠다.