[문자열 문제] 가장 긴 '반복 부분 문자열' 길이 구하기

참고 문제 출처
www.acmicpc.net/problem/1605

1605번: 반복 부분문자열

문제

알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분 문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분 문자열을 '반복 부분 문자열'이라고 부르자.

문자열이 주어지면, 가장 긴 '반복 부분 문자열'의 길이를 구하는 프로그램을 작성하시오.

 

입력 (+테스트 케이스 추가, -문자열의 길이 제공X)

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 첫 번째 줄에 길이가 200,000 이하인 문자열이 주어진다.

이 문자열은 알파벳 소문자만으로 이루어져 있다.

 

출력

첫째 줄에 가장 긴 '반복 부분 문자열'의 길이를 출력한다.

만일 '반복 부분 문자열'이 하나도 존재하지 않는다면 0을 출력한다.

입력 예제	출력 예제
4                                                  //TestCase 개수 tellmetellmetetetetetetellme     //TestCase 1 입력 sabcabcfabc                             //TestCase 2 입력 trutrutiktiktappop                     //TestCase 3 입력 abcdef                                  //TestCase 4 입력	11        //TestCase 1 출력 3          //TestCase 2 출력 4          //TestCase 3 출력 0          //TestCase 4 출력

첫 번째 문자열에서는 "etetetetete"가 부분 문자열로 나온다.

두 번째 문자열에서는 “abc”가 부분 문자열로 세 번 나온다.

세 번째 문자열에서는 “trut”혹은 “tikt”가 답이 된다.

네 번째 문자열에는 두 번 이상 등장하는 부분 문자열이 없다.

 

풀이

해당 문제를 원초적으로 접근해서 주어진 문자열의 모든 부분 문자열을 다 알아내면 O(N^2)이 나올 것이고, 각각을 다 비교하려면 O(N)이 걸리므로 총 O(N^3)이 소요되는데, 주어진 문제의 문자열 최대길이는 N=20만이므로 이 방법으로는 효율이 좋지 않습니다. O(NlogN) 정도 이하의 방법을 찾아야겠죠.

 

해당 문제를 풀 수 있는 방법은 2가지 정도 있을 것 같은데요,

 

첫 번째 방법으로는 Suffix Array와 Longest Common Prefix Array를 이용하는 방법입니다.

LCPA에 있는 값들 중 최댓값이 원하는 답이 됩니다.

 

두 번째 방법으로는 이분 검색을 이용한 방법이 있습니다. 길이가 L인 부분 문자열이 두 번 이상 나온다면, L 이하인 부분 문자열에 대해서도 두 번 이상 나오는 부분 문자열이 존재하는 것이 당연하기 때문입니다.

즉 어떠한 길이 L을 답으로 정해서 길이가 L인 부분 문자열이 두 번 나오는 경우가 있는지 빠르게 볼 수 있으면 되는데, 이는 Hashing을 이용해 쉽게 확인할 수 있습니다. 

 

 

💡 저는 두 번째 방법으로 문제를 풀어보았습니다.

 

위에 언급하였 듯이 길이가 L인 부분 문자열이 두 번 이상 나온다면, L 이하인 부분 문자열에 대해서도 두 번 이상 나오는 부분 문자열이 존재합니다. ( TestCase의 1번을 예로 보면 etetetetete라는 문자열이 두 번 나왔고 이 길이가 11인데, etetetetet라는 문자열도 2번 이상 나왔고, 이 길이는 10입니다.)

이러한 성질을 이용해서 파라메트릭 서치로 반복 문자열이 존재하는 가장 긴 길이 L을 구하려고 합니다. 즉, T(L)라는 문제를 logL번만 풀면 T(L) == True를 만족하는 최대 L을 구할 수 있습니다.

 

이때 T(L) == True인지 즉, 길이 L인 문자열이 두 번 이상 나오는 경우가 있는지는 해시값을 비교하는 방식을 사용합니다. 길이 L인 모든 부분 문자열의 hash 값을 비교해서 동일한 hash값이 있으면, 반복 부분 문자열이 있는 것입니다.

 

모든 hash 값을 구하면 시간이 많이 걸리므로, 첫 번째만 L만큼의 선형으로 구하고, 두 번째부터는 슬라이딩 윈도우 테크닉을 이용해서 추가되는 글자에 해시값만 추가하고, 떨어져 나가는 글자의 해시값만 빼주는 식으로 O(1)로 구할 수 있습니다.

이렇게 구해진 부분 문자열들의 hash 값은 quick sort로 정렬해두면 동일한 값이 있는지 빠르게 확인할 수 있습니다.

 

문제 풀이 코드

#define MAX_CHAR 200001
#include <stdio.h>

char str[MAX_CHAR];
int strLen = 0;
int resultLen = 0;
long long hashValue[MAX_CHAR];
const long long MOD = 100000000005381ll;
int comp(int st, int en) {
	int i = st;
	while (i < en) {
		if (hashValue[i] == hashValue[i+1]) 
			return 1;
		else i++;
	}
	return 0;
}

void quickSort(int first, int last)
{
	int pivot;
	int i;
	int j;
	long long temp;

	if (first < last)
	{
		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (hashValue[i] <= hashValue[pivot] && i < last)
			{
				i++;
			}
			while (hashValue[j] > hashValue[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = hashValue[i];
				hashValue[i] = hashValue[j];
				hashValue[j] = temp;
			}
		}

		temp = hashValue[pivot];
		hashValue[pivot] = hashValue[j];
		hashValue[j] = temp;

		quickSort(first, j - 1);
		quickSort(j + 1, last);
	}
}

int isPossible(int ln) {
	for (int i = 0; i < MAX_CHAR; i++) hashValue[i] = 0;
	long long hash = 0;
	for (int i = 0; i < ln; i++) {
		hash = (hash * 26 + str[i] - 'a') % MOD;
	}
	hash = (hash + MOD) % MOD;
	hashValue[0] = hash;

	long long firstStrHash = 1;
	for (int b = 0; b < ln - 1; b++) {
		firstStrHash = (firstStrHash *26) % MOD;
	}
	int j = 1;
	for (j = 1; j <= strLen - ln; j++) {
		hash = (hash - (str[j - 1] - 'a')*firstStrHash) % MOD;
		hash = (hash * 26 + (str[j+ln-1] - 'a')) % MOD;
		hash = (hash + MOD) % MOD;
		hashValue[j] = hash;
	}
	quickSort(0, j - 1);

	return comp(0, j - 1);
}

void binarySearch()
{
	int low = 0, high = strLen-1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (isPossible(mid))
		{
			resultLen = mid;
			low = mid + 1;
		}
		else
		{
			high = mid -1;
		}
	}
}

int main(void)
{
	int test_case;
	int T;
	freopen("sample_input.txt", "r", stdin);
	setbuf(stdout, NULL);
	scanf("%d", &T);

	for (test_case = 1; test_case <= T; ++test_case)
	{
		strLen = 0;
		resultLen = 0;
		scanf("%s", &str);
		while (str[strLen] != 0) { strLen++; }
		binarySearch();
		printf("%d\n", resultLen);
	}
	return 0; 
}

 

문제 풀이에 사용한 알고리즘 

[파라메트릭 서치] Parametric Search의 이해 및 구현

[파라메트릭 서치] Parametric Search의 이해 및 구현

[Hash 알고리즘] 해시의 이해 및 구현

[Hash 알고리즘] 해시의 이해 및 구현