(알고리즘) 서로 다른 부분 문자열의 수

* 길이가 n인(n<=4000)인 문자열은 최대 (n+1)*n/2개의 부분 문자열을 가질 수 있다.

하지만 이들이 모두 다른 것은 아니다.
예를들어, "banana"는 "ana"를 두번 "n"을 두 번포함한다. 문자열이 주어질 때 이들의 서로 다른 부분 문자열의 수를 세는 문제를 풀어보자.

가장 간단한 방법은 각 부분 문자열을 직접 만들어보면서 이들을 집합 자료 구조 안에 넣는것이다. O(n^2)개의 부분 문자열이 있고, 이들을 set<>자료구조에 넣으려면 각 문자열마다 O(lgn)번의 비교를 해야 한다. 각 문자열을 비교하는 데 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n^3lgn)이 된다. 해시를 이용해서 필요한 비교횟수를 O(1)로 줄이면 시간복잡도를 O(n^3)으로 줄일수도 있지만 부족하다.

접미사 배열로 이 문제를 풀 수 있다. 우선 주어진 문자열의 접미사배열을 생성한다.
이때 S의 모든 부분 문자열들은 이 접미사들의 접두사로 표현 할 수 있다.
이 의미는 만약 "banana"의 접미사 배열 중 a와 ana가 있다고 하면 ana는 접미사이며 이때 3개의 접두사가 존재한다. ana의 접두사로 a, an, ana를 만들 수 있다. 하지만 a하나로 부분 문자열을 만들 수 있으므로 ana와 a는 a라는 부분문자열이 중복된다 그러므로 이것을 뺴는 것이다.
길이 m인접미사에는 m개의 접두사가 있을 테니, 부분문자열이 중복이 없다면 각 접미사의 길이를 모두 더해서 부분 문자열의 수를 얻을 수 있다.