Boj 2179) 비슷한 단어

문제

백준 2179

설명

BruteForce 로도 풀리지만 LCP Array 를 써서 풀어보려고 했더니 나름 까다로워서 정리한다.

문제에서 다행히 문자열을 모두 다르게 주어 중복 문자열 판단은 하지 않아도 된다.

하지만 주어진 순서 상 가장 빠른 것을 선택하는 것이 어려웠다.

• 문자열들을 합칠 때 맨 앞에 사전순으로 가장 빠른 문자를 삽입해 Suffix Array 의 앞의 N 개가 완전한 문자열이 되게 한다.
• 문자열의 뒤에 가장 늦는 문자를 삽입해 문자열을 구분짓는다.
• LCP Array 를 구할 때 문자열 단위를 넘어서지 않도록 조건을 추가한다.
• 최대 LCP 값을 갖는 Suffix Array Index 를 모두 저장한 후 Suffix Array 값을 이용해 정렬을 하면 가장 앞의 값이 사전순으로 가장 빠르다. 이때 공통문자열이 앞쪽일 수도 있고 뒤쪽을 수도 있으므로 둘 중 최솟값을 저장한다.
• LCP 가 유지된다면 바로 Suffix Array 에서 인접하지 않아도 되므로 Suffix Array 상에서 탐색을 앞뒤로 한다.

시간 복잡도

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

코드

template<int SIZE = 2050002, int CSIZE = 30>
struct SuffixArray
{
	string src; int len = -1;
	int sa[SIZE], lcp[SIZE];

	// 내부사용값
	int rk[SIZE], cnt[SIZE], 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 rk[a + o] < rk[b + o];
		return  a + o > b + o;
	}

	void CountSort()
	{
		int m = max(rk[sa[len - 1]] + 1, CSIZE) + 1;
		fill(cnt, cnt + m, 0);
		for (int i = 0; i < len; i++) cnt[i + o < len ? rk[i + o] + 1 : 0]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (int i = len - 1; i >= 0; i--) tmp[--cnt[i + o < len ? rk[i + o] + 1 : 0]] = i;

		fill(cnt, cnt + m, 0);
		for (int i = 0; i < len; i++) cnt[rk[i]]++;
		for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
		for (int i = len - 1; i >= 0; i--) sa[--cnt[rk[tmp[i]]]] = tmp[i];
	}

	void Init()
	{
		len = src.size();
		int p, i;

		//Manber-Myers Algorithms
		for (i = 0; i < len; i++) rk[i] = src[i] - ('a' - 1);
		for (p = 0, o = 1; p + 1 < len; o <<= 1)
		{
			CountSort();
			p = tmp[sa[0]] = 0;
			for (int i = 1; i < len; i++)
				tmp[sa[i]] = Cmp(sa[i - 1], sa[i]) ? ++p : p;
			swap(tmp, rk);
		}

		// Kasai Algorithms
		// 여기서는 len 이 1 인경우 rank 가 알파벳 오프셋이 되어 작동하지 않음에 주의
		int num = 0;
		for (int i = 0; i < len; i++)
		{
			int k = rk[i];
			if (k) {
				while (src[i + num] == src[sa[k - 1] + num] && src[i + num] != 'z' + 1) num++;
				lcp[k] = num;
				if (num) num--;
			}
		}
	}
};
SuffixArray sf;

string Get(int rk)
{
	string res;
	int cur = sf.sa[rk] + 1;
	while (cur < sf.len && sf.src[cur] <= 'z') res += sf.src[cur++];
	return res;
}

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		string a; cin >> a;
		sf.src += 'a' - 1;
		sf.src += a;
		sf.src += 'z' + 1;
	}
	sf.Init();

	int max_lcp = 0; vector<int> rks;
	for (int i = 1; i < n; i++)
	{
		if (max_lcp <= sf.lcp[i])
		{
			if (max_lcp < sf.lcp[i])
			{
				max_lcp = sf.lcp[i];
				rks.clear();
			}
			if (max_lcp == sf.lcp[i])
				rks.push_back(i);
		}
	}
	sort(rks.begin(), rks.end(), [](int a, int b) { return min(sf.sa[a], sf.sa[a - 1]) < min(sf.sa[b], sf.sa[b - 1]); });

	int pivot = rks[0]; rks.clear();
	int cur = pivot;
	while (cur >= 0 && sf.lcp[cur] >= max_lcp) rks.push_back(--cur);
	cur = pivot;
	while (cur < n && sf.lcp[cur] >= max_lcp) rks.push_back(cur++);

	sort(rks.begin(), rks.end(), [](int a, int b) { return sf.sa[a] < sf.sa[b]; });
	cout << Get(rks[0]) << '\n' << Get(rks[1]);
}