LCP 배열

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

LCP 배열
유형 배열
고안자 Manber & Myers (1990)
빅 오 표기법에 따른
시간 복잡도
평균 최악
공간
구현

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

나이브한 알고리즘편집

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

Kasai의 알고리즘편집

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

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

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

 

 

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

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

 

 

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

 

이다.

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

 

 

 


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