LCP 배열

LCP 배열 유형 배열 고안자
 colspan="2"    빅 오 표기법에 따른시간 복잡도 평균 최악 공간   구현  

컴퓨터 과학에서, 최장 공통 접두사 배열(), 혹은 LCP 배열은 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다.

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

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

일 경우: 최장 공통 접두사의 길이는 항상 0 이상이므로 자명하게 성립한다.

일 경우: 현재 탐색하고 있는 접미사 과, 접미사 배열에서 의 바로 이전 인덱스에 있는 접미사 을 다음과 같이 표현할 수 있다.

이때 은 공통된 첫 문자, 는 첫 문자 뒤로 공통된 길이 의 문자열, 와 는 서로 다른 문자열이다.

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

이때 과 은 사전 순으로 정렬되어 있었으므로, 공통된 첫 번째 문자를 뺀 과 에 대해서도 이 성립한다.

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

이다. 이때 의 인덱스는 보다 작고 의 인덱스는 보다 1 작으므로 접미사 배열의 성질에 의해 가 성립하고, 와  모두 를 접두사로 가지므로 그 사이에 있는  역시 를 접두사로 가지게 된다. 즉, 최장 공통 접두사의 길이는 의 길이인  이상이다.

분류:배열
분류:문자열 자료 구조