Boj 11478) 서로 다른 부분 문자열의 갯수

문제

백준 11478

설명

주어진 입력의 크기가 작아서 BruteForce 로도 풀리지만 LCP Array 를 응용한 방법을 기록한다.

ababc 의 Suffix 와 그에 따른 Prefix 는 다음과 같다.

ababc
  ababc
  abab
  aba
  ab
  a
abc
  abc
  ab
  a
babc
  babc
  bab
  ba
  b
bc
  bc
  b
c
  c

여기서 ababc 와 abc 에서 Longest Common Prefix 의 크기만큼 Prefix 가 중복됨에 주목하자.

위를 통해 모든 부분문자열의 갯수에서 lcp 의 값들을 빼주면 정답임을 유추할 수 있다.

시간 복잡도

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

코드

template<int SIZE = 2001, 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
		// 여기서는 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]) num++;
				lcp[k] = num;
				if (num) num--;
			}
		}
	}
};
SuffixArray sf;

char s[MAXIN];

int main()
{
	cin >> sf.src;
	sf.Init();

	int ans = sf.len * (sf.len+1)/2;
	for (int i = 0; i < sf.len; i++)
		ans -= sf.lcp[i];
	cout << ans;

}