맨버-마이어스 알고리즘

접미사 배열을 n * lg(n) ^ 2 시간으로 찾게 해주는 알고리즘인데 간단히 소개하면

t = 1, 2, 4, 8 .... 2^n - 1 순으로 증가하며 이 t번째 문자를 기준으로 접미사를 정렬해 나가는 것이다.

 

struct MM_Comparator {
	const vector<int>& group;
	int t;
	MM_Comparator(const vector<int>& _group, int _t) : group(_group), t(_t) {}

	bool operator() (int a, int b) {
		if (group[a] != group[b]) return group[a] < group[b];
		return group[a + t] < group[b + t];
	}
};
vector<int> MamberMiaus(const string& s) {
	int n = s.size();

	int t = 1;
	vector<int> group(n + 1);
	for (int i = 0; i < n; ++i) group[i] = s[i]; // 첫번째 글자를 기준으로 정렬
	group[n] = -1; // t 길이의 글자를 그룹에 배정하기 위한 임시값

	vector<int> perm(n);
	for (int i = 0; i < n; ++i) perm[i] = i; // 접미사 배열의 순번 저장
	while (t < n) {
		MM_Comparator compareUsing2T(group, t);
		sort(perm.begin(), perm.end(), compareUsing2T);

		t *= 2;
		if (t >= n) break;

		vector<int> newGroup(n + 1);
		newGroup[perm[0]] = 0;
		newGroup[n] = -1;
		for (int i = 1; i < n; ++i)
		{
			if (compareUsing2T(perm[i - 1], perm[i]))
				newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
			else
				newGroup[perm[i]] = newGroup[perm[i - 1]];
		}
		group = newGroup;
	}
	return perm;
}

 

다른 블로그를 보면 정리가 잘 되어있지만 왜 2의 지수승으로 비교를 해나가도 문제가 해결되는지 알아내는데 상당한 시간이 걸려서 까먹기 전에 정리해 본다

 

1. t = 1일때 기준으로 정렬이 된다면 반드시 길이가 1일 접미사는 독립적인 그룹으로 들어가 있다

2. t = 2일때 기준으로 정렬이 된다면 길이가 2일 접미사 는 독립적인 그룹이며 3일 접미사도 1일 접미사가 이미 독립적인 그룹수를 가지고 있으므로 독립적입 그룹에 배정된다 즉 이 때 반드시 1, 2, 3은 독립적인 그룹에 들어가 있다

3. t = 4일때 4일 접미사는 독립적인 그룹이며 1, 2 ,3 이 독립적인 그룹이므로 5, 6, 7 그룹도 독립적인 그룹에 배정된다

4. t = n일때 n은 독립적인 그룹이며 n - 1 이 이미 독립적인 그룹이므로 n * 2 - 1그룹도 독립적인 그룹에 배정된다.

 

이 동작의 원리로 인하여 이 알고리즘이 동작하게 된다고 생각하는데 논문은 읽어보지 않아서 확실하다고는 정확하지 않을수도 있다