[Algorithm] 20 문자열 - 9

예제: 원형 문자열

그림 20.7 원형 문자열

길이 n(n≤4000) 인 문자열을 끝과 끝이 연결된 원형으로 써봅시다. 이 문자열은 항상 시계 방향으로 읽는데, 시작 위치가 어디인지는 정해져 있지 않으므로 n 가지 방법으로 읽을 수 있습니다. 이 중 사전순으로 가장 앞에 오는 문자열은 무엇일까요?

예를 들면, 그림 20.7의 문자열은 맨 위에 있는 a에서부터 읽기 시작하면 “aavadakedavr” 이 됩니다.

이 문제를 푸는 가장 당연한 방법은 n 개의 후보를 하나하나 만들어 보고 이들 중 가장 사전순으로 앞에 있는 것을 찾는 것입니다. 그러면 n-1 번의 비교를 하고, 각 비교에는 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n²)이 됩니다.

접미사 배열을 이용해 이 문제를 풀 수 있을까?

원형으로 되어있어 어려워 보이지만, 이럴 때 유용하게 쓸 수 있는 트릭이 있다.

재하의 금고 문제에서 처럼 S를 두 번 반복한 문자열 S²을 만드는 것이다.

이 때 S를 읽을 수 있는 방법은 모두 S²의 부분 문자열이 된다.

1. S²의 접미사 배열을 만든다.
2. 길이가 n 이상인 접미사 중 가장 앞에 오는 것을 찾아낸다.

그러면 접미사 배열을 만드는 시간인 O(nlog²n) 시간에 답을 계산할 수 있다.

// 사전순으로 갖장 앞에 오는 s의 회전 결과를 구한다.
string minShift(const string& s){
	string s2 = s + s;
	vector<int> a = getSuffixArray(s2);
	for(int i = 0; i < a.size(); ++i){
		if(a[i] <= s.size())
			return s2.substr(a[i], s.size());
	// 여기로 올 일은 없어야 한다.
	return "__oops__";
}

접미사의 시작 위치가 b 이하라면 해당 접미사의 길이가 n 이상인 것을 알 수 있다.

이 접미사의 첫 n 글자가 답이다.

bananabanana 의 접미사배열

ex) bananabanana

s2	a	a.size	i	a[i] ≤ s.size()
bananabanana	…	12	0	12 ≤ 6
			1	6 ≤ 6
bananabanana