LCP 배열 문서 원본 보기

{{위키데이터 속성 추적}}
{{번역중 | en:LCP array}}
{| class="infobox" style="width: 22em"
! colspan="3" style="font-size: 125%; text-align: center;" | LCP 배열
|-
! [[자료구조의 목록|유형]]
| colspan="2" | [[배열]]
|-
! 고안자
{{!}} colspan="2" {{!}}  {{harvtxt|Manber|Myers|1990}}
|-
! colspan="3" class="navbox-abovebelow" | [[빅 오 표기법]]에 따른<br />[[시간 복잡도]]
|-
|
| 평균
| 최악
|-
! 공간
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|-
! 구현
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|}

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

== LCP 배열을 구현하는 알고리즘 ==
=== 나이브한 알고리즘 ===
접미사 배열에서 인접한 두 접미사끼리 직접 비교한다. 한 쌍의 접미사에서 공통되는 접두사의 길이는 <math>\mathcal{O}(n)</math>에서 구할 수 있으므로 총 시간 복잡도는 <math>\mathcal{O}(n^2)</math>가 된다.

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

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

2. 만약 <math>k</math>가 2 이상이면 다음과 같이 표현할 수 있다.

<math>S_{prev1} = c_1 C_2 D</math>

<math>S_{now1} = c_1 C_2 F</math>

이때 <math>S_{now1}</math>은 현재 탐색하고 있는 접미사이고, <math>S_{prev1}</math>은 접미사배열에서 자신의 이전 인덱스에 있는 접미사이다.
그리고 구성요소인 <math>c1</math>은 공통된 첫 문자, <math>C_2</math>는 첫 문자 뒤로 공통된 문자열, <math>D</math>와 <math>F</math>는 서로 다른 문자열이다. 또한 <math>C_2</math>의 길이는 <math>k-1</math>이 된다.

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

<math>{S'}_{prev1} = C_2 D</math>

<math>{S'}_{now1} = C_2 F</math>

이제 다음 탐색에서 최장공통접미사의 길이가 <math>k-1</math>이상이라는 것을 보일 것이다. 다음으로 탐색할 접미사 <math>S_{now2}</math>는 길이가 1만큼 짧아졌으므로

<math>S_{now2} = {S'}_{now1} = C_2 F</math>

이다.

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

<math>{S'}_{prev1} = C_2 D</math>

<math>{S}_{prev2} = C_2 E</math>

<math>{S}_{now2} = C_2 F</math>


<math>S_{now1}</math>과 <math>S_{prev1}</math>는 사전순으로 정렬되어있었으므로, 첫번째 문자를 뺀 <math>{S'}_{now1}</math>과 <math>{S'}_{prev1}</math>에 대해서도 순서관계가 성립하게 된다.
즉, 항상 <math>{S'}_{prev1}</math>는 <math>{S'}_{now1}</math>보다 앞선 인덱스에 있게 된다.
또한 <math>{S'}_{prev1}</math>의 인덱스는 항상 <math>{S'}_{now1} = S_{now2}</math>''의 인덱스''<math> - 1</math>보다 작으므로 <math>S_{prev2}</math>는 항상 <math>S_{now2}</math>와 <math>{S'}_{prev1}</math> 사이에 있게 된다.
이때, 접미사 배열은 모든 접미사에 대해 사전순으로 정렬된 배열이기 때문에 <math>{S'}_{prev1} \leq S_{prev2} < S_{now2}</math>가 성립하므로 <math>S_{prev2}</math> 역시 <math>C_2</math>를 공통으로 가지게 된다.
즉, 최장공통접미사의 길이는 <math>C_2</math>의 길이인 <math>k-1</math>보다 길다.

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