Write a program to extract the longest repeated substring in a given string.

주어진 문자열에서 반복되는 가장 긴 문자열을 추출하자. 문자열의 길이를 n이라고 했을 때 가장 무식한 방법은 모든 가능한 문자열을 다 구해서 반복되는 문자열을 찾고 긴 문자열을 출력하면 된다. 비교 대상인 두 문자열의 시작점을 i, j라고하고 문자열의 길이를 k라고 하고, 비교할 수 있고 문자열을 비교하는 것 또한 k만큼 필요하므로 대략 O(n^4)이 나온다. 어쨌든, 좋지 않다.

이 문제에 접근하기 위해서 사용되는 것이 suffix array라는 것이다. 문자열에서의 각 시작점들의 인덱스를 값(element)으로 가지는 배열을 말한다. 말로 써놓으면 이해하기 어렵고 간단하게 예를 들면 'banana'라는 문자열이 있을 때 'banana'는 0번 인덱스부터 시작한 것이고, 'anana'는 1번 인덱스부터 시작한 것이다. 또한 'na'의 경우 4번 인덱스부터 시작한 것이다. 이러한 0, 1, 4 등의 값을 가지는 배열을 suffix array라고 한다.

a[] = {"banana", "anana", "nana", "ana", "na", "a"}

위와 같은 식으로 값을 가리키는 셈인데, 이것을 정렬하면

a[] = {"a", "ana", "anana", "banana", "na", "nana"}

와 같은 꼴이 된다. 이제 앞뒤 문자열만 비교하면 순서대로 몇 개의 문자가 일치하는지 쉽게 구할 수 있다. 이 경우 "ana"와 "anana"에서 3자리 문자열 "ana"가 가장 긴 반복되는 문자열이 된다. 이제 시간 복잡도는 O(n*nlogn)이 된다. n은 문자열 비교에서, nlogn은 정렬에서 온 수치이다.

소스 코드 상에서는 compare 함수에서 *(char**)a 를 사용하는 부분이 까다로왔다. 포인터에 대해서 좀 알게 되었나 싶었더니 여전히 잘 모르는 것 같다. 좀 더 알아봐야겠다. Programming Pearls에서 보고 감탄했는데, 알고랭이 좀 했다하는 애들은 중학생들도 아는 알고리즘이라는 것을 알고 나니 부끄럽다. -_-;


댓글을 달아 주세요