LCP 배열: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →Kasai의 알고리즘: 설명 추가 |
잔글 →Kasai의 알고리즘: 내용 추가 |
||
31번째 줄:
=== Kasai의 알고리즘 ===
Kasai의 알고리즘은 접미사 배열이 사전순으로 정렬되어있다는 특성을 이용한 알고리즘이다. 이 알고리즘은 가장 긴 접미사(원본 문자열)부터 길이가 짧아지는 순서대로 접미사를 탐색하며 최장공통접두사의 길이를 구한다. 이 알고리즘의 핵심적인 생각은 현재 탐색하고 있는 접미사의 최장공통접두사 길이가 <math>k</math>라면 다음에 탐색하는 접미사의 최장공통접두사의 길이는 <math>k-1</math> 이상이라는 것이다. 이는 다음과 같이 증명할 수 있다.
1. 최장공통접두사의 길이가 0 이상이라는 것은 자명하므로 <math>k</math>가 0 또는 1인 경우에 대해서 성립한다.
2. 만약 <math>k</math>가 2 이상이면 다음과 같이 표현할 수 있다.
<math>S_{prev} = c_1 C_2 D</math>
<math>S_{now} = c_1 C_2 E</math>
이때 <math>c1</math>은 공통된 첫 문자, <math>C_2</math>는 첫 문자 뒤로 공통된 문자열, <math>D</math>와 <math>E</math>는 서로 다른 문자열이다.
| |||