LCP 배열

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 정의
4. LCP 배열 구축 알고리즘
5. 응용
6. 추가 정보
- 6.1. 범위 최소 쿼리 (RMQ)
참조

1. 개요

LCP 배열은 문자열의 접미사 배열에서 인접한 두 접미사 간의 최장 공통 접두사 길이를 저장하는 배열이다. 1993년 처음 소개되었으며, 문자열 검색 알고리즘의 실행 시간을 개선하는 데 사용된다. LCP 배열은 접미사 트리 구축, 패턴 검색, 최장 반복 부분 문자열 찾기, LZ77 압축 등 다양한 문자열 처리 문제에 응용된다. LCP 배열을 효율적으로 계산하기 위한 다양한 알고리즘이 개발되었으며, 카사이 알고리즘 등이 대표적이다.

2. 역사

LCP 배열은 문자열 검색 알고리즘의 실행 시간을 개선하기 위해 1993년 우디 만버와 진 마이어스에 의해 접미사 배열과 함께 소개되었다.

3. 정의

문자열 $S=s_1,s_2,\ldots s_{n-1}\$$ 의 접미사 배열을 $A$ 라고 하자. 여기서 $S$ 의 길이는 $n$ 이고, $\$$ 는 문자열의 끝을 나타내는 특수한 센티넬 문자로, 다른 어떤 문자보다 사전적으로 앞에 오는 문자라고 가정한다. $S[i,j]$ 는 $i$ 번째 문자부터 $j$ 번째 문자까지 이어지는 $S$ 의 부분 문자열을 나타낸다. 따라서 $S[A[i], n]$ 는 $S$ 의 접미사 중에서 사전 순서로 $i$ 번째에 해당하는 접미사이다.

두 문자열 $v$ 와 $w$ 사이의 최장 공통 접두사(Longest Common Prefix, LCP)의 길이를 $\operatorname{lcp}(v,w)$ 로 나타내자. LCP 배열 $H$ 는 길이가 $n$ 인 정수 배열이다. 배열의 첫 번째 값인 $H[1]$ 은 비교할 이전 접미사가 없으므로 정의되지 않는다. $1 < i \leq n$ 범위의 $i$ 에 대해 $H[i] = \operatorname{lcp}(S[A[i-1], n], S[A[i], n])$ 로 정의된다. 즉, $H[i]$ 는 접미사 배열에서 사전 순서로 $i$ 번째 접미사와 바로 앞( $i-1$ 번째) 접미사 간의 최장 공통 접두사의 길이를 저장한다.
접미사 배열과 LCP 배열의 차이점:

접미사 배열: 각 접미사가 전체 문자열 내에서 사전적으로 몇 번째 순서인지를 나타낸다.
LCP 배열: 사전 순서로 정렬된 접미사 배열에서, 서로 이웃한 두 접미사 간의 최장 공통 접두사의 길이를 저장한다.

예를 들어, 문자열

S = \textrm{banana\$}

를 생각해보자.

i	1	2	3	4	5	6	7
S[i]	b	a	n	a	n	a	$

이 문자열의 접미사 배열 $A$ 는 각 접미사의 시작 위치를 사전 순서대로 나열한 것이다.

i (사전 순서)	1	2	3	4	5	6	7
A[i] (시작 위치)	7	6	4	2	1	5	3

사전 순서로 정렬된 접미사들은 다음과 같다.

i	A[i]	접미사 (S[A[i], n])
1	7	$
2	6	a$
3	4	ana$
4	2	anana$
5	1	banana$
6	5	na$
7	3	nana$

이제 LCP 배열 $H$ 를 구해보자. $H[i]$ 는 $i$ 번째 접미사와 $i-1$ 번째 접미사 간의 최장 공통 접두사의 길이이다.

i	1	2	3	4	5	6	7
접미사 S[A[i-1], n]	-	$	a$	ana$	anana$	banana$	na$
접미사 S[A[i], n]	$	a$	ana$	anana$	banana$	na$	nana$
H[i] = lcp(S[A[i-1], n], S[A[i], n])	정의 안됨	0	1	3	0	0	2

예를 들어, $H[4]=3$ 은 사전 순서로 세 번째 접미사인 $S[A[3], 7] = S[4, 7] = \textrm{ana\$}$ 와 네 번째 접미사인 $S[A[4], 7] = S[2, 7] = \textrm{anana\$}$ 사이의 최장 공통 접두사가 $\textrm{ana}$ 이고 그 길이가 3임을 의미한다. $H[1]$ 은 비교할 이전 접미사가 없기 때문에 정의되지 않는다.

4. LCP 배열 구축 알고리즘

LCP 배열을 구성하는 알고리즘은 크게 두 가지 방식으로 나눌 수 있다. 하나는 접미사 배열을 만들 때 LCP 배열도 함께 계산하는 방식이고, 다른 하나는 이미 만들어진 접미사 배열을 이용하여 LCP 값을 계산하는 방식이다. 다양한 알고리즘들이 개발되었으며, 각기 다른 시간 복잡도와 공간 복잡도 특성을 가진다. 대표적인 알고리즘으로는 나이브 알고리즘, 카사이 알고리즘 등이 있으며, 이 외에도 여러 개선된 알고리즘들이 존재한다. 자세한 내용은 아래 하위 섹션들에서 설명한다.

4. 1. 나이브 알고리즘

접미사 배열에서 인접한 두 접미사를 직접 비교하여 최장 공통 접두사(LCP)의 길이를 계산하는 가장 기본적인 방법이다. 한 쌍의 접미사에서 공통되는 접두사의 길이는

\mathcal{O}(n)

시간에 구할 수 있다. 접미사 배열에는

n

개의 접미사가 있으므로, 인접한 쌍은

n-1

개가 존재한다. 따라서 모든 인접한 쌍에 대해 비교를 수행하면, 전체 LCP 배열을 계산하는 데 필요한 총 시간 복잡도는

\mathcal{O}(n^2)

가 된다. 이 방법은 개념적으로 간단하지만, 문자열의 길이가 길어질 경우 계산 시간이 매우 오래 걸려 비효율적이다.

4. 2. 카사이(Kasai) 알고리즘

카사이(Kasai)의 알고리즘은 접미사 배열이 사전순으로 정렬되어 있다는 특성을 이용하여 LCP 배열을 효율적으로 계산하는 방법이다. 이 알고리즘은 시간 복잡도

O(n)

으로 LCP 배열을 구축할 수 있다.

알고리즘의 핵심 아이디어는 다음과 같다. 접미사 배열에서 어떤 접미사(

S_{now1}

)와 바로 앞의 접미사(

S_{prev1}

) 사이의 최장 공통 접두사(LCP) 길이가

k

라고 할 때,

S_{now1}

에서 첫 글자를 제외한 다음 접미사(

S_{now2}

)와 그 바로 앞의 접미사(

S_{prev2}

) 사이의 LCP 길이는 최소

k-1

이라는 것이다.

이는 다음과 같이 설명할 수 있다.

1. LCP 값은 항상 0 이상이므로,

k

가 0 또는 1일 때는 자명하게 성립한다.

2.

k

가 2 이상인 경우를 생각해보자.

$S_{prev1}$ 과 $S_{now1}$ 의 LCP 길이가 $k$ 이므로, 이 둘은 처음 $k$ 개의 문자가 동일하다. 이를 $S_{prev1} = c_1 C_2 D$ , $S_{now1} = c_1 C_2 F$ 로 표현할 수 있다. 여기서 $c_1$ 은 첫 문자, $C_2$ 는 길이가 $k-1$ 인 공통 문자열, $D$ 와 $F$ 는 첫 문자가 서로 다른 나머지 문자열이다. 접미사 배열의 순서에 따라 $D$ 는 $F$ 보다 사전순으로 앞선다.
각 접미사에서 첫 문자를 제외한 문자열을 ${S'}_{prev1} = C_2 D$ , ${S'}_{now1} = C_2 F$ 라고 하자.
다음으로 탐색할 접미사는 $S_{now1}$ 에서 첫 문자를 제외한 $S_{now2} = {S'}_{now1} = C_2 F$ 이다.
접미사 배열은 모든 접미사를 포함하며 사전순으로 정렬되어 있다. $S_{prev1} < S_{now1}$ 이므로, 첫 문자를 제외해도 사전순 관계는 유지되어 ${S'}_{prev1} < {S'}_{now1} = S_{now2}$ 이다.
$S_{now2}$ 바로 이전의 접미사를 $S_{prev2}$ 라고 하면, ${S'}_{prev1}$ 은 $S_{now2}$ 보다 앞에 위치하므로, ${S'}_{prev1} \leq S_{prev2} < S_{now2}$ 관계가 성립한다.
${S'}_{prev1}$ 과 $S_{now2}$ 는 모두 $C_2$ (길이 $k-1$ )를 공통 접두사로 가진다. 따라서 그 사이에 위치하는 $S_{prev2}$ 역시 최소한 $C_2$ 를 접두사로 가져야 한다.
결과적으로 $S_{prev2}$ 와 $S_{now2}$ 의 LCP 길이는 최소 $k-1$ 이 된다.

카사이 알고리즘은 이 원리를 이용하여, 가장 긴 접미사부터 시작하여 순차적으로 각 접미사의 LCP 값을 계산한다. 이전 단계에서 계산된 LCP 값을 활용하여 다음 LCP 값 계산 범위를 줄여나가기 때문에 전체 LCP 배열을 선형 시간(

O(n)

) 안에 완성할 수 있다. 이 알고리즘은 한국어와 같이 문자가 복잡하게 조합되는 텍스트에서도 효율적으로 작동한다.

4. 3. 기타 알고리즘

LCP 배열을 구성하는 알고리즘은 크게 두 가지 방식으로 나눌 수 있다. 첫 번째는 LCP 배열을 접미사 배열의 부가적인 결과물로 함께 계산하는 방식이고, 두 번째는 이미 구성된 접미사 배열을 활용하여 LCP 값을 계산하는 방식이다.

Manber와 Myers (1993)는

O(n \log n)

시간에 LCP 배열과 접미사 배열을 동시에 계산하는 알고리즘을 제시했다. Kärkkäinen과 Sanders (2003)는 자신들의

O(n)

시간 접미사 배열 구축 알고리즘을 수정하여 LCP 배열도 함께 계산할 수 있음을 보였다. 반면, Kasai 등 (2001)은 주어진 텍스트와 접미사 배열을 이용하여 LCP 배열을 계산하는 최초의

O(n)

시간 알고리즘(FLAAP)을 개발했다.

Kasai 등의 알고리즘은 효율적이지만, 각 텍스트 기호가 1바이트, 접미사 배열이나 LCP 배열의 각 항목이 4바이트를 차지한다고 가정할 때, 총

13n

바이트의 메모리를 사용하는 단점이 있다. 이는 원본 데이터(텍스트, 접미사 배열, LCP 배열)가 필요로 하는 공간인

9n

바이트보다 크다. 이러한 문제를 해결하기 위해 Manzini (2004)는 Kasai 등의 알고리즘을 개선하여 메모리 사용량을

9n

바이트로 줄인 lcp9 알고리즘을 제안했다. 또한 Kärkkäinen, Manzini, Puglisi (2009)는 Kasai의 알고리즘을 다른 방식으로 개선하여 실행 시간을 향상시킨

\Phi

-알고리즘을 개발했다. 이 알고리즘은 일반적인 LCP 배열 대신, 값들이 사전순이 아닌 텍스트에서의 순서대로 나타나는 '순열된' LCP(PLCP) 배열을 구축한다.

Gog와 Ohlebusch (2011)는 이론적인 시간 복잡도는

O(n^2)

으로 상대적으로 느리지만, 실제 수행 속도는 앞서 언급된 여러 알고리즘보다 빠른 두 가지 알고리즘을 제시하기도 했다.

2012년 기준으로 가장 빠른 선형 시간 LCP 배열 구성 알고리즘은 Fischer (2011)에 의해 개발된 것으로 알려져 있으며, 이는 Nong, Zhang, Chan (2009)이 개발한 빠른 접미사 배열 구성 알고리즘 중 하나인 SA-IS를 기반으로 한다. 이후 Fischer와 Kurpicz (2017)는 Yuta Mori의 DivSufSort 알고리즘을 기반으로 하여 더욱 빠른 LCP 배열 구성 알고리즘을 개발했다.

5. 응용

LCP 배열은 접미사 배열과 함께 사용되어 다양한 문자열 처리 문제 해결에 중요한 역할을 한다. 특히 접미사 트리 관련 연산을 효율적으로 시뮬레이션하는 데 유용하다. 예를 들어, 접미사 배열과 LCP 배열만으로 접미사 트리의 상향식 순회를 시뮬레이션할 수 있으며, 추가적인 자료 구조를 결합한 "향상된 접미사 배열"을 이용하면 접미사 트리의 하향식, 상향식, 접미사 링크를 이용한 순회 등 모든 종류의 트리 순회를 시뮬레이션할 수 있다. 또한, LCP 배열을 범위 최소 쿼리(RMQ)를 위해 전처리하면 향상된 접미사 배열의 공간 요구 사항을 줄일 수 있다. 결과적으로, 접미사 트리 알고리즘으로 해결 가능한 문제는 향상된 접미사 배열로도 해결할 수 있다.

패턴 검색에서도 LCP 배열은 성능 향상에 기여한다. 길이가 $m$ 인 패턴 $P$ 를 길이가 $n$ 인 문자열 $S$ 에서 찾는 문제는 접미사 배열만 사용하면 $O(m \log n)$ 시간이 걸리지만, LCP 배열 정보를 활용하면 $O(m + \log n)$ 시간으로 개선할 수 있으며, 더 나아가 최적의 $O(m)$ 시간 복잡도를 달성하는 방법도 존재한다. 이는 접미사 트리를 사용하는 것과 동일한 검색 속도이다.

이 외에도 LCP 배열은 다음과 같은 다양한 응용 분야에서 활용된다.

압축 접미사 트리의 핵심 구성 요소로서, 접미사 링크나 최소 공통 조상(LCA) 쿼리와 같은 접미사 트리의 전체 기능을 제공하는 데 사용된다.
접미사 배열과 함께 사용하여 Lempel-Ziv LZ77 팩터리제이션을 $O(n)$ 시간에 계산할 수 있다.
문자열 $S$ 내에서 두 번 이상 나타나는 가장 긴 부분 문자열을 찾는 최장 반복 부분 문자열 문제를 접미사 배열과 함께 $\Theta(n)$ 시간에 해결할 수 있다. 이는 LCP 배열의 최댓값을 찾는 것만으로 가능하다.

LCP 배열을 활용한 구체적인 알고리즘, 예를 들어 접미사 트리를 효율적으로 구축하거나 패턴 검색 속도를 높이는 방법 등은 하위 섹션에서 더 자세히 살펴볼 수 있다.

5. 1. 접미사 트리 구축

문자열

S=s_1,s_2,\ldots s_n\$

의 접미사 배열

A

와 LCP 배열

H

가 주어졌을 때, 이 문자열의 접미사 트리

ST

는 다음 아이디어를 기반으로 O(n) 시간에 구축될 수 있다. 먼저 사전순으로 가장 작은 접미사에 대한 부분 접미사 트리로 시작하여, 접미사 배열이 제공하는 순서대로 다른 접미사들을 반복적으로 삽입한다.

ST_{i}

를

0\leq i \leq n

에 대한 부분 접미사 트리라고 하자. 또한,

d(v)

를

ST_i

의 루트에서 노드

v

까지 이어지는 모든 경로 레이블을 연결한 문자열의 길이로 정의한다.

구축은 루트 노드만으로 구성된 트리인

ST_0

에서 시작한다.

i

번째 단계에서 접미사

A[i+1]

을 부분 트리

ST_i

에 삽입하기 위해, 가장 최근에 삽입된 리프 노드(접미사

A[i]

에 해당)에서 시작하여 루트 방향으로 "가장 오른쪽" 경로를 따라 올라간다. 이 과정은 경로 길이

d(v)

가

H[i+1]

이하인 가장 깊은 노드

v

에 도달할 때까지 계속된다. (

H[i+1]

은 접미사

A[i]

와

A[i+1]

의 최장 공통 접두사(LCP)의 길이를 나타낸다.)

이때 두 가지 경우로 나눌 수 있다.

경우 1: $d(v)=H[i+1]$

이 경우는 루트에서 노드

v

까지의 경로 레이블이 정확히 접미사

A[i]

와

A[i+1]

의 최장 공통 접두어와 같음을 의미한다.

이때는

A[i+1]

을 나타내는 새 리프 노드

x

를

v

의 자식으로 추가한다. 그리고

v

와

x

를 잇는 에지

(v,x)

에는

S[A[i+1]+H[i+1], n]

을 레이블로 지정한다. 이 레이블은 접미사

A[i+1]

에서 이미 루트-v 경로로 표현된 최장 공통 접두어를 제외한 나머지 부분이다.

이렇게 하여 부분 접미사 트리

ST_{i+1}

이 생성된다.

케이스 2 ( $d(v) < H[i+1]$ ): 접미사 $nana\$$ 를 추가하려면 이전에 삽입된 접미사 $na\$$ 로의 에지를 분할해야 한다. 새 내부 노드로의 새 에지에는 접미사 $na$$ 와 $nana\$$ 의 가장 긴 공통 접두어가 레이블로 지정된다. 두 리프를 연결하는 에지에는 접두어의 일부가 아닌 "나머지" 접미사 문자가 레이블로 지정된다.

경우 2: $d(v) < H[i+1]$

이 경우는 루트에서 노드

v

까지의 경로 레이블이

A[i]

와

A[i+1]

의 최장 공통 접두어보다 짧다는 것을 의미한다. 즉, 최장 공통 접두어의 나머지 "누락된" 부분은

v

아래의 "가장 오른쪽" 에지 레이블에 포함되어 있다. 따라서 해당 에지를 "분할"해야 한다.

w

를

ST_i

의 가장 오른쪽 경로 상에 있는

v

의 자식 노드라고 하자. 분할 과정은 다음과 같다.

1. 기존 에지

(v,w)

를 삭제한다.

2. 새로운 내부 노드

y

를 생성하고,

v

와

y

사이에 에지

(v,y)

를 추가한다. 이 에지의 레이블은

S[A[i]+d(v), A[i]+H[i+1]-1]

로, 이는

A[i]

와

A[i+1]

의 최장 공통 접두어 중 루트-v 경로에 포함되지 않았던 "누락된" 부분이다. 이제 루트에서

y

까지의 경로 레이블은 정확히

A[i]

와

A[i+1]

의 최장 공통 접두어를 나타낸다.

3. 기존 노드

w

를 새로 생성된 내부 노드

y

의 자식으로 연결한다. 즉, 에지

(y,w)

를 만들고, 레이블은

S[A[i]+H[i+1], A[i]+d(w)-1]

로 지정한다. 이 레이블은 원래 에지

(v,w)

의 레이블 중에서, 새로 만들어진 에지

(v,y)

의 레이블로 사용되지 않은 "나머지" 부분이다.

4.

A[i+1]

을 나타내는 새 리프 노드

x

를 추가하고,

y

와

x

사이에 에지

(y,x)

를 추가한다. 이 에지의 레이블은

S[A[i+1]+H[i+1], n]

으로, 접미사

A[i+1]

에서 루트-y 경로(최장 공통 접두어)를 제외한 나머지 부분이다.

5. 이렇게 하여 부분 접미사 트리

ST_{i+1}

이 생성된다.

이 알고리즘의 전체 실행 시간은 간단한 상각 분석을 통해

O(n)

으로 제한됨을 보일 수 있다. 각 단계

i

에서

ST_i

의 "가장 오른쪽" 경로를 따라 올라갈 때 방문하는 노드들(마지막 노드

v

제외)은,

A[i+1]

이 새 리프로 트리에 추가되면서 "가장 오른쪽" 경로에서 벗어나게 된다. 이렇게 경로에서 벗어난 노드들은 이후의 어떤 단계

j>i

에서도 다시 방문되지 않는다. 따라서 모든 노드를 통틀어 최대

2n

번의 이동(traversal)만 발생하므로 전체 시간 복잡도는

O(n)

이 된다.

5. 2. 패턴 검색

LCP 배열은 주어진 텍스트에서 특정 패턴이 몇 번 나타나는지 효율적으로 찾는 데 사용될 수 있다.

길이가

m

인 패턴

P

를 길이

N

인 텍스트

T

에서 찾을 때, 접미사 배열만을 사용하면 이진 검색을 통해

O(m \log N)

시간이 걸린다. 각 비교마다 패턴

P

전체(최대

m

개 문자)를 접미사 배열의 현재 항목과 비교해야 할 수 있기 때문이다. 하지만 LCP 배열 정보를 추가로 활용하면, 이 검색 시간을

O(m + \log N)

으로 개선할 수 있다. 추가적인 자료 구조를 사용하면 실행 시간을 최적의

O(m)

시간으로 더욱 개선하는 방법도 제시되었다.

O(m + \log N)

개선은 LCP 배열의 특수한 버전인 LCP-LR 배열을 사용하여 이진 검색 과정을 최적화함으로써 이루어진다. 표준 이진 검색에서는 탐색 범위

(L, \dots, R)

의 중간점

M

과 패턴

P

를 비교하여 다음 탐색 범위를 결정한다. 이 과정에서

P

와

M

위치의 접미사 간에 문자 비교가 반복적으로 발생할 수 있다.

LCP-LR 배열은 이진 검색 중에 만날 수 있는 특정 범위들(

(L, \dots, M)

,

(M, \dots, R)

)에 대해

\mathrm{lcp}(L, M)

과

\mathrm{lcp}(M, R)

값을 미리 계산해 둔 배열이다. 이를 이용하면

O(1)

시간에 필요한 LCP 값을 조회할 수 있다. 만약 이전 단계에서

P

와

M

의 접미사가 처음

k

개 문자에서 일치함(

\mathrm{lcp}(P, M) = k

)을 알았다고 가정하자. 다음 단계에서 새로운 중간점

M'

을 고려할 때, 미리 계산된

\mathrm{lcp}(M, M')

값과

k

를 비교하여 불필요한 문자 비교를 건너뛸 수 있다.

경우 1: $k < \mathrm{lcp}(M, M')$ : $P$ 와 $M$ 의 공통 접두사 길이( $k$ )가 $M$ 과 $M'$ 의 공통 접두사 길이보다 짧다. 이는 $M'$ 의 $(k+1)$ 번째 문자가 $M$ 과 같다는 의미이다. 만약 $P$ 가 $M$ 보다 사전순으로 크다면, $M'$ 보다도 클 것이므로 오른쪽( $M', \dots, R$ )에서 탐색을 계속한다. (문자 비교 불필요)
경우 2: $k > \mathrm{lcp}(M, M')$ : $P$ 는 $M$ 과 $M'$ 사이의 공통 접두사보다 더 긴 공통 접두사를 $M$ 과 가진다. 이 경우 $M'$ 은 $P$ 보다 사전순으로 클 것이므로 왼쪽( $M, \dots, M'$ )에서 탐색을 계속한다. (문자 비교 불필요)
경우 3: $k = \mathrm{lcp}(M, M')$ : $M$ 과 $M'$ 모두 처음 $k$ 개 문자에서 $P$ 와 일치한다. 다음 탐색 방향을 결정하기 위해 $P$ 와 $M'$ 을 $(k+1)$ 번째 문자부터 비교한다.

이러한 최적화를 통해 패턴

P

의 각 문자는 텍스트의 어떤 문자와도 최대 한 번만 비교되도록 보장된다. 따라서 총 문자 비교 횟수는

m

으로 제한되며, 전체 검색 시간 복잡도는

O(m + \log N)

이 된다.

LCP-LR 배열 자체는 표준 LCP 배열로부터

O(N)

시간과

O(N)

공간으로 미리 계산될 수 있다.

결과적으로, 향상된 이진 검색을 두 번 수행하여(패턴

P

로 시작하는 접미사들의 시작 위치와 끝 위치를 찾기 위해) 패턴

P

와 일치하는 접미사 배열 상의 구간을 찾을 수 있다. 이 구간의 길이는 패턴

P

가 텍스트

T

에 나타나는 총 횟수와 같다.

5. 3. 기타 응용

LCP 배열은 접미사 배열과 함께 다양한 문자열 처리 문제 해결에 중요한 역할을 한다. 특히 접미사 트리 관련 연산을 효율적으로 수행하는 데 사용된다. 몇몇 문자열 처리 문제는 다음과 같은 종류의 트리 순회로 해결할 수 있다.

전체 접미사 트리의 하향식 순회
접미사 트리의 서브트리의 상향식 순회
접미사 링크를 사용한 접미사 트리 순회

접미사 배열과 LCP 배열만 사용하여 접미사 트리의 상향식 순회를 시뮬레이션하는 방법이 제시되었다. 또한, LCP 배열과 추가적인 자료 구조를 사용하여 접미사 배열을 향상시키고, 이 "향상된 접미사 배열"을 사용하여 접미사 트리 순회의 세 가지 종류 모두를 시뮬레이션하는 방법도 설명되었다. 범위 최소 쿼리를 위해 LCP 배열을 전처리하면 향상된 접미사 배열의 공간 요구 사항을 줄일 수 있다. 따라서 접미사 트리 알고리즘으로 해결할 수 있는 모든 문제는 "향상된 접미사 배열"을 사용하여 해결할 수도 있다.

길이가

m

인 패턴

P

가 길이가

n

인 문자열

S

의 부분 문자열인지 결정하는 데는 접미사 배열만 사용하면

O(m \log n)

시간이 걸린다. LCP 정보를 추가로 사용하면 이 경계를

O(m + \log n)

시간으로 개선할 수 있다. 이 실행 시간을 더욱 개선하여 최적의

O(m)

시간을 달성하는 방법도 제시되었다. 따라서 접미사 배열과 LCP 배열 정보를 사용하면 접미사 트리를 사용하는 것만큼 빠르게 결정 쿼리에 답변할 수 있다.

LCP 배열은 접미사 링크 및 최소 공통 조상 쿼리와 같은 전체 접미사 트리 기능을 제공하는 압축 접미사 트리의 필수적인 부분이다. 또한, 접미사 배열과 함께 사용하여 Lempel-Ziv LZ77 팩터리제이션을

O(n)

시간에 계산할 수 있다.

길이가

n

인 문자열

S

에 대한 최장 반복 부분 문자열 문제는 접미사 배열

A

와 LCP 배열을 모두 사용하여

\Theta(n)

시간에 해결할 수 있다. LCP 배열을 선형으로 스캔하여 최대 값

v_{max}

와

v_{max}

가 저장된 해당 인덱스

i

를 찾는 것으로 충분하다. 두 번 이상 발생하는 최장 부분 문자열은

S[A[i],A[i]+v_{max}-1]

로 주어진다.

6. 추가 정보

(내용 없음)

6. 1. 범위 최소 쿼리 (RMQ)

LCP 배열

H

는 접미사 배열

A

에서 사전적으로 인접한 접미사 쌍들의 최장 공통 접두사(LCP) 길이만을 저장한다. 하지만 임의의 두 접미사, 예를 들어 문자열

S

의

i

번째 위치에서 시작하는 접미사

S[i,n]

과

j

번째 위치에서 시작하는 접미사

S[j,n]

사이의 최장 공통 접두사 길이

\operatorname{lcp}(S[i,n], S[j,n])

를 구해야 할 때가 있다.

이 값은 역 접미사 배열

A^{-1}

(

A[k]= p \Leftrightarrow A^{-1}[p]= k

, 즉 접미사

S[p,n]

는 접미사 배열

A

의

k

번째 항목임)와 LCP 배열

H

에 대한 범위 최소 쿼리(Range Minimum Query, RMQ)를 이용하여

O(1)

의 상수 시간에 계산할 수 있다.

원리는 다음과 같다. 접미사 배열

A

는 접미사들을 사전 순서로 정렬한 것이므로, 두 접미사

S[i,n]

과

S[j,n]

사이 (접미사 배열 상에서

A^{-1}[i]

위치와

A^{-1}[j]

위치 사이)에 있는 모든 접미사들은

S[i,n]

과

S[j,n]

의 공통 접두사를 반드시 접두사로 가져야 한다. 따라서,

S[i,n]

과

S[j,n]

의 최장 공통 접두사 길이는, 접미사 배열에서 두 접미사 사이에 위치하는 모든 인접한 접미사 쌍들의 LCP 값들 중 가장 작은 값과 같다.

만약

A^{-1}[i] < A^{-1}[j]

라고 가정하면, 이 최소값은 LCP 배열

H

의 구간

[A^{-1}[i]+1, A^{-1}[j]]

에서의 최솟값이 된다. LCP 배열

H

에 대해 범위 최소 쿼리를 미리 계산해두면(전처리), 특정 구간의 최솟값을 상수 시간

O(1)

에 찾을 수 있다.

결과적으로, 임의의 두 위치

i, j

(

A^{-1}[i] < A^{-1}[j]

)에 대해 두 접미사

S[i,n]

과

S[j,n]

의 최장 공통 접두사 길이는 다음 공식을 통해 구할 수 있다:

\operatorname{LCP}(i,j) = H[\operatorname{RMQ}_H(A^{-1}[i]+1, A^{-1}[j])]

여기서

\operatorname{RMQ}_H(l, r)

은 LCP 배열

H

의 구간

[l, r]

에서 최솟값을 찾는 연산을 의미한다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com