[BOJ] 11478번: 서로 다른 부분 문자열의 개수

https://www.acmicpc.net/problem/11478

문제의 예시에서 일단 Suffix Array를 만들어놓고 시작하겠습니다.

ababc

abc

babc

bc

c

이 때 빨간색 부분이 윗 문자와의 LCP입니다. 빨간색 부분은 중복되기 때문에 횟수를 세면 안되고, 검은색을 포함하면 중복되지 않기 때문에 각각에 대해서 중복되지 않은 문자열은 아래와 같이 추출이 가능합니다.

ababc -> a / ab / aba / abab / ababc

abc -> abc

babc -> b  / ba / bab / babc

bc -> bc

c -> c

즉 LCP의 갯수만큼 횟수가 줄어들게 되니까 len*(len+1)/2 - sum of LCP가 정답이 됩니다.

https://github.com/blisstoner/BOJ/blob/master/11478.cpp