LCP 배열

LCP배열 (Longest Common Prefix array, 최장 공통 접두사 배열)은 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다.

LCP 배열을 구현하는 알고리즘

나이브한 알고리즘 
접미사 배열에서 인접한 두 접미사끼리 직접 비교한다. 한 쌍의 접미사에서 공통되는 접두사의 길이는 에서 구할 수 있으므로 총 시간 복잡도는 가 된다.

Kasai의 알고리즘 
Kasai의 알고리즘은 접미사 배열이 사전순으로 정렬되어있다는 특성을 이용한 알고리즘이다. 이 알고리즘은 가장 긴 접미사(원본 문자열)부터 길이가 짧아지는 순서대로 접미사를 탐색하며 최장공통접두사의 길이를 구한다. 이 알고리즘의 핵심적인 생각은 현재 탐색하고 있는 접미사의 최장공통접두사 길이가 라면 다음에 탐색하는 접미사의 최장공통접두사의 길이는  이상이라는 것이다. 이는 다음과 같이 증명할 수 있다.

1. 최장공통접두사의 길이가 0 이상이라는 것은 자명하므로 가 0 또는 1인 경우에 대해서 성립한다.

2. 만약 가 2 이상이면 다음과 같이 표현할 수 있다.

이때 은 현재 탐색하고 있는 접미사이고, 은 접미사배열에서 자신의 이전 인덱스에 있는 접미사이다.
그리고 구성요소인 은 공통된 첫 문자, 는 첫 문자 뒤로 공통된 문자열, 와 는 서로 다른 문자열이다. 또한 의 길이는 이 된다.

각 접미사에서 첫번째 문자를 뺀 문자열에는 를 붙이기로 하자. 따라서 다음과 같다.

이제 다음 탐색에서 최장공통접미사의 길이가 이상이라는 것을 보일 것이다. 다음으로 탐색할 접미사 는 길이가 1만큼 짧아졌으므로

이다.

이때 접미사 배열에서 다음과 같은 순서가 성립한다.

과 는 사전순으로 정렬되어있었으므로, 첫번째 문자를 뺀 과 에 대해서도 순서관계가 성립하게 된다.
즉, 항상 는 보다 앞선 인덱스에 있게 된다.
또한 의 인덱스는 항상 의 인덱스보다 작으므로 는 항상 와  사이에 있게 된다.
이때, 접미사 배열은 모든 접미사에 대해 사전순으로 정렬된 배열이기 때문에 가 성립하므로  역시 를 공통으로 가지게 된다.
즉, 최장공통접미사의 길이는 의 길이인 보다 길다.

배열
문자열 자료 구조