Boj 13012) 접미사 배열 1

문제

백준 13012

설명

문자열의 한 문자를 바꾸었을 때 Suffix Array 가 유지되려면 어떻게 해야할까? 이는 Suffix 간의 비교를 재귀적으로 생각하면 쉽게 정리할 수 있다. 바로 sa[i] 의 첫글자와 같으면 sa[i]+1 의 첫글자와 비교하고 이를 반복한다는 것이다. 그러면 sa[i] 의 한 문자를 바꾸었을 때 기존의 Suffix Array 내의 순서를 유지한다면 모든 Suffix 간의 비교가 유지됨을 알 수 있다.

sa[i] 의 첫글자를 바꾼다고 해보자. 문제에서 요구하는 것은 사전순으로 더 빠른 경우이다. 그럼 첫글자를 사전순으로 더 줄여야한다. 이 때 경우의 수를 세가지로 나눌 수 있다.

• 사전순으로 줄이면 sa[i-1] 의 첫글자보다 사전순으로 앞인 경우. 이 경우는 Suffix Array 를 유지할 수 없다.
• 사전순으로 줄여도 sa[i-1] 의 첫글자보다 사전순으로 뒤인 경우. 이 경우는 Suffix Array 내의 위치를 유지함이 자명하다.
• 사전순으로 줄였을 때 sa[i-1] 의 첫글자보다 사전순으로 같은 경우. 이 경우는 sa[i-1]+1 가 sa[i]+1 보다 Suffix Array 에 오는 순서가 앞선다면 가능하다. 단 Suffix 가 한문자로 이루어져 있다면 따로 처리해야한다.

또한 모든 문자열이 'a' 이상인 경우 전체적으로 알파벳을 한칸 앞으로 옮기면 되므로 이를 고려해야한다.

이를 반영하면 아래와 같은 결과가 나온다.

시간 복잡도

O(\(\mathrm{N}\log{ \mathrm{N}}^2\))

코드

template<int SIZE = 100>
struct SuffixArray
{
	string src; int len = -1;
	int sa[SIZE], rk[SIZE], rk_tmp[SIZE];
	int o = 1;

	inline bool Cmp(int a, int b)
	{
		if (rk[a] != rk[b]) return rk[a] < rk[b];
		if (a + o >= len || b + o >= len)
			return a + o > b + o;      // 초과하는 Suffix 가 앞쪽에 오도록
		return  rk[a + o] < rk[b + o];
	}

	void Init()
	{
		len = src.size();
		for (int i = 0; i < len; i++) { sa[i] = i; rk[i] = src[i]; }

		//Manber-Myers Algorithms
		for (o = 1; o < len; o <<= 1)
		{
			// Quick Sort
			sort(sa, sa + len, bind(&SuffixArray::Cmp, this, placeholders::_1, placeholders::_2));

			// Regrouping
			rk_tmp[sa[0]] = 0;
			for (int i = 1; i < len; i++)
				rk_tmp[sa[i]] = Cmp(sa[i - 1], sa[i]) ? rk_tmp[sa[i - 1]] + 1 : rk_tmp[sa[i - 1]];
			swap(rk_tmp, rk);
		}
	}
};
SuffixArray sf;

bool Check()
{
	if (sf.src[sf.sa[0]] > 'a') return true;
	for (int i = 1; i < sf.len; i++)
	{
		char prev = sf.src[sf.sa[i - 1]];
		char cur = sf.src[sf.sa[i]];

		if (prev < cur-1) return true;
		else if (prev == cur-1)
		{
			// a   |   aa
			// ba  |   b
			if (sf.sa[i] + 1 == sf.len) continue;
			if (sf.sa[i - 1] + 1 == sf.len || sf.rk[sf.sa[i-1]+1] <= sf.rk[sf.sa[i]+1])
				return true;
		}
	}
	return false;
}

int main(void)
{
	cin >> sf.src;
	sf.Init();
	cout << Check();
}

관련 문제

접미사 배열 2

t has the same Suffix Array