Boj 9249) 최장 공통 부분 문자열

문제

백준 9249

설명

두 문자열을 구분자를 두어서 이어서 Suffix Tree 를 둔 뒤, lcp[] 의 최대를 구하되 앞뒤가 T 와 S 사이에 있는지 체크하여 답을 구했다.

라빈-카프에 이분탐색으로도 풀린다던데…

시간 복잡도

O(\(\vert \mathrm{S} \vert + \vert \mathrm{T} \vert\))

코드

template<int SIZE = 500002, int CSIZE = 26>
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';
		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
		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]) num++;
				lcp[k] = num;
				if (num) num--;
			}
		}
	}
};
SuffixArray p;

int main()
{
	fastio;
	string a, b;
	cin >> a >> b;
	p.src = a + char('z'+1) + b;
	p.Init();

	int n = -1, max_v = -1;
	for(int i = 1; i < p.len ; i++)
		if (p.sa[i-1] > a.size() == p.sa[i] < a.size() && max_v < p.lcp[i])
			max_v = p.lcp[i]; n = i;
	
	cout << p.lcp[n] << endl;
	cout << p.src.substr(p.sa[n], p.lcp[n]);
}