[C] 문자열에서 반복되는 가장 긴 부분 문자열

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에서 보고 감탄했는데, 알고랭이 좀 했다하는 애들은 중학생들도 아는 알고리즘이라는 것을 알고 나니 부끄럽다. -_-;

#include <stdio.h>
#include <string.h>
#include <stdlib.h>	// for malloc

int compare(const void *a, const void *b)
{
	return strcmp(*(char**)a, *(char**)b);
}

int complen(const void *a, const void *b) 
{
	int len, max = strlen((char*)a);
	if (strlen((char*)b) < max) max = strlen((char*)b);
	for (len = 0;len < max; len++) {
		if (((char*)a)[len] != ((char*)b)[len])
			return len;
	}
}

int main() 
{
	char buf[] = "abcdaabcdefabcf";
	int len = strlen(buf);
	int maxlen = 0;
	int idx = 0; 
	int tmp = 0;
	int i = 0;

	char *sa[len];	

	for (i = 0; i < len; i++)
		sa[i] = &buf[i];
	qsort(sa, len, sizeof(char*), compare);

	for (i = 0; i < len - 1; i++) {
		tmp = complen(sa[i], sa[i+1]);
		if (tmp > maxlen) {
			maxlen = tmp;
			idx = i;
		}
	}

	char *longstr = (char*)malloc(sizeof(char)*maxlen+1);
	strncpy(longstr, sa[idx], maxlen);
	printf("idx: %d maxlen: %d str: %s\n", idx, maxlen, longstr);

	free(longstr);

	return 0;
}