백준 11478 서로 다른 부분 문자열의 개수

http://deque.tistory.com/82

위를 통해 lcp를 구한다.

그리고 주어진 string이 가질 수 있는 모든 부분 문자열의 갯수에서 lcp의 총 합을 뺀다.

그것이 정답인 이유는 다음과 같다.

1. 어떤 부분 문자열은 어떤 접미사의 접두사이다.

2. 그런데 어떤 두 접미사끼리 서로 접두사가 같은 부분이 있다면 그 부분은 부분문자열중 생김새가 같은 문자열이다.

3. 따라서 총 부분문자열의 갯수에서 생김새가 같은 문자열(lcp)의 모든 갯수(lcp의 합)을 뺀다.

ababc를 예로 들어보자

ababc의 접미사는

ababc

abc

babc

bc

c

이다.

따라서 모든 부분문자열은

ababc => a, ab, aba, abab, ababc

abc => a, ab, abc

babc => b, ba, bab, babc

bc => b, bc

c => c

이다.

한편, 여기서 ababc와 abc는 앞의 두글자가 같다(lcp[1] = 2).

그 말은, ababc가 가지고 있는 접두사와 abc가 가지고 있는 접두사중 두개의 쌍이 겹친다는 뜻이다.

따라서 총 부분문자열 15개중 2개는 겹치는 것이므로 13이다.

또한 babc와 bc의 앞 한글자가 같다(lcp[3] = 1).

따라서 마찬가지로 13에서 1을 뺀다

그리하여 정답은 12이다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char S[1001];
int sa[1001], pos[1001], temp[1001], lcp[1001];
int delta, N;

bool cmp(int i, int j) {
	if (pos[i] != pos[j]) return pos[i] < pos[j];
	i += delta;
	j += delta;
	if (i < N && j < N) return pos[i] < pos[j];
	else return i > j;
}

int main() {
	scanf("%s", S);
	N = strlen(S);

	//pos[x] = S[x:-1]의 순번
	//temp[x] = x순번의 그룹번호
	//sa[x] = x순번의 suffix의 S에서의 index
	for (int i = 0; i < N; i++) {
		pos[i] = S[i] - 'a';
		sa[i] = i;
	}
	delta = 1;
	while (true) {
		memset(temp, 0, sizeof(temp));
		sort(sa, sa + N, cmp);
		for (int i = 0; i < N - 1; i++) {
			temp[i + 1] = temp[i] + cmp(sa[i], sa[i + 1]);
		}
		for (int i = 0; i < N; i++) {
			pos[sa[i]] = temp[i];
		}
		if (temp[N - 1] == N - 1) break;
		delta *= 2;
	}

	int sameCount = 0;
	for (int i = 0; i < N; i++) {
		if (sameCount > 0) sameCount--;
		if (sameCount < 0) sameCount = 0;
		if (pos[i] == 0) continue;
		int j = sa[pos[i] - 1];
		while (true) {
			if ((i + sameCount) > N || (j + sameCount) > N) break;
			if (S[i + sameCount] == S[j + sameCount]) sameCount++;
			else break;
		}
		lcp[pos[i]] = sameCount;
	}

	int sum = 0;
	for (int a : lcp) {
		sum += a;
	}
	int all = N* (N + 1) / 2;
	printf("%d", all - sum);

	return 0;
}