문자열에 몇 개의 다른 부분 문자열이 있습니까?

Question

길이 n의 문자열 t가 주어 졌을 때, t의 다른 하위 문자열 수를 계산하는 알고리즘을 O (n)에서 설계해야합니다.

Answer 1

1. 입력 문자열에 대한 접미사 자동 완성을 작성하십시오.

2. maxLength[v]이 v 상태로 루트에서 가장 긴 경로는 maxLength[v] - maxLength[suffixLink[v]] for all states v 및 suffixLink[v]의 합을 찾기는이 상태에 대한 접미사 링크입니다.

선형 시간에 접미사 자동 완성을 만드는 것은 잘 알려진 문제입니다. 두 번째 부분은 단순한 순회입니다. 따라서 총 시간 복잡도는 O(n)입니다.