문자열 핵심 자료구조 suffix array와 lcp(longest common prefix)배열 구하는법 배우기(Manber-Myers, kasai)

https://cp-algorithms.com/string/suffix-array.html#definition

Suffix Array - Algorithms for Competitive Programming

 

https://gumgood.github.io/suffix-array-and-lcp

접미사 배열과 LCP 배열(Suffix Array and LCP Array) - Gumgood

 

 

https://ko.wikipedia.org/wiki/%EC%A0%91%EB%AF%B8%EC%82%AC_%EB%B0%B0%EC%97%B4

접미사 배열 - 위키백과, 우리 모두의 백과사전

 

 

https://blog.myungwoo.kr/57

Suffix Array와 LCP

 

 

https://www.geeksforgeeks.org/kasais-algorithm-for-construction-of-lcp-array-from-suffix-array/

­­kasai’s Algorithm for Construction of LCP array from Suffix Array - GeeksforGeeks

 

 

1. 정의

 

길이 n인 문자열 s에 대하여 s의 i번째 suffix는 s의 부분문자열 s[i,i+1,...,n-1]을 말한다.

 

suffix array는 주어진 문자열의 모든 suffix를 사전순으로 정렬한 후에, 해당 suffix들의 시작 index를 모아놓은 배열이다.

 

예를 들어 s = abaab라고 하자.

 

모든 suffix는 다음과 같이 구해진다.

시작 인덱스	suffix
0	abaab
1	baab
2	aab
3	ab
4	b

 

이렇게 구한 suffix를 사전 순으로 정렬하면..

 

시작 인덱스	suffix
2	aab
3	ab
0	abaab
4	b
1	baab

 

이렇게 정렬한 뒤 시작 인덱스를 모아놓은 배열 [2,3,0,4,1]을 suffix array라고 부른다.

 

생물정보학, 데이터 압축 등 많은 분야에서 널리 사용되면서 문자열 관련 문제에서 자주 사용된다.

 

가장 쉽게 구현하는 방법은 위와 같이 naive하게 suffix를 모두 구하고 정렬한 다음 인덱스를 가지고 오는 방법으로 $O(N^{2}logN)$ 방법이 있다.

 

 

2. 연습문제1

 

11656번: 접미사 배열 (acmicpc.net)

11656번: 접미사 배열

 

n의 최대가 1000이라 단순히 suffix를 모두 모으고 정렬하면 된다

 

$O(N^{2}logN)$은 1000만정도라 1초에 충분

 

s = input()

suffix_array = []

for i in range(len(s)):
    
    suffix_array.append(s[i:])

suffix_array.sort()

for suffix in suffix_array:
    
    print(suffix)

 

 

하지만 N이 너무 커지면 이 방법은 시간이 너무 느려 실전성이 없다..

 

N=10000 정도만 되도 힘들다

 

현재 가장 빠르게 구하는 방법이 O(N)이라고 하지만 너무 어려워 쓰이지 않고 널리 알려진 방법은 O(NlogN)방법이라고 한다

 

 

3. Manber-Myers 알고리즘

 

가장 널리 알려진 $O(Nlog^{2}N)$만에 suffix array를 구성하는 방법

 

핵심은 1,2,4,8,...의 2의 거듭제곱꼴 $2^{k}$길이의 부분문자열을 기준으로 정렬한다

 

이렇게 O(logN)번의 O(NlogN) 정렬을 반복하여 $O(Nlog^{2}N)$만에 구성할 수 있다고 한다

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

정렬을 하는 기준을 보통 "rank"라고 부른다.

 

어떤 접미사에서 접두사를 빼더라도 여전히 다른 접미사가 된다는 성질을 이용한다.

 

이 알고리즘은 매 단계마다 접미사에 rank를 부여하고 이를 이용해 정렬한다.

 

매 k단계의 rank는 앞에서부터 $2^{k-1}$글자의 순서 정보를 포함하고 있다

 

----------------------------------------------------------------------------------------------------------------------------------------------

 

예를 들어 i번째 접미사가 GATAGACA라고 하자.

 

앞에서부터 d개의 문자는 d/2개의 문자의 연속된 두 부분으로 구성되어 있다.

 

 

 

이 알고리즘은 매 단계마다 1,2,4,8,...개의 문자를 기준으로 정렬한다고 했다.

 

그러니까 현재 앞에서부터 d개의 문자를 기준으로 정렬한다는 것은 이미 이전 단계에서는 d/2개의 문자를 기준으로 정렬한 상태이다.

 

또한 앞쪽의 d/2개의 문자를 제외한 i번째 접미사와 i + d/2번째 접미사는 서로 같다는 것을 관찰할 수 있다.

 

(이게 아마 "어떤 접미사에서 접두사를 빼더라도 여전히 다른 접미사가 된다는 성질을 이용한다." 이 뜻일듯?)

 

i번째 접미사의 앞부터 d개의 문자를 (i번째 접미사 순서, i+d/2번째 접미사 순서)로 나타내고,

 

이를 다른 j번째 접미사와 비교하기 위해 (j번째 접미사 순서, j+d/2번째 접미사 순서)로 나타내서

 

두 순서쌍을 비교한다면 두 접미사간 대소를 O(1)에 판단하여 정렬할 수 있다.

 

 

4. 예시로 이해해보기

 

s = abaab의 접미사 배열을 구해보자.

 

먼저 앞에서부터 d = 1개의 글자를 기준으로 정렬한다.

 

오직 앞에서부터 1개의 글자만 보고 정렬한다는 의미가 된다.

 

모든 접미사는 abaab, baab, aab, ab, b 5개 있는데...

 

앞에서부터 1개의 글자는 A아니면 B이므로.. A가 붙은 접미사가 먼저 B가 붙은 접미사가 먼저 온다.

 

그러면 (ab, abaab, aab)와 (b,baab) 두 종류로 나뉘는데.. 각 내부에서 순서는 일단 알아서 해도 된다

 

 

1) 그런 다음 rank를 부여하는데 동일한 순서의 접미사는 동일한 rank를 부여한다.

 

2) 또한 빠를수록 더 작은 값을 부여한다.

 

3) 실제 rank가 어떤 값으로 부여하는지는 중요한 것은 아니다..

 

아래 표는 1,2로 부여했지만 3,4로 부여하든 4,5로 부여하든 상관은 없다.

 

그저 순서만 지켜준다면...

 

suffix array(i번째 접미사)	suffix	rank
3	ab	1
0	abaab	1
2	aab	1
4	b	2
1	baab	2

 

다음 단계는 이전에는 d = 1개의 글자를 기준으로 정렬했기 때문에 2배한 d = 2개의 글자를 기준으로 정렬한다.

 

어떻게 하냐면, i번째 접미사의 순서 정보를 (i번째 접미사의 rank, i + d/2번째 접미사의 rank)로 바꿔준다.

 

예를 들어 ab의 경우 현재 rank = 1이고 i + d/2번째 접미사는 b인데 b의 rank는 2니까 (1,2)이다.

 

그런데 b의 경우 i+d/2번째 접미사가 빈 문자열이다. 이런 경우는 0으로 부여한다.

 

즉 b의 경우는 (2,0)이 된다.

 

suffix array(i번째 접미사)	suffix	order pair
3	ab	(1,2)
0	abaab	(1,2)
2	aab	(1,1)
4	b	(2,0)
1	baab	(2,1)

 

aab의 경우 i+d/2번째 접미사는 ab이다. 이것의 rank는 1이기 때문에 (1,1)이 된다.

 

baab의 경우 i + d/2번째 접미사는 aab이다. 이것의 rank는 1이므로 (2,1)이 된다.

 

이렇게 얻은 순서쌍 order pair를 기준으로 정렬한다.

 

(1,1), (1,2), (1,2), (2,0), (2,1)로 정렬이 되겠지

 

suffix array(i번째 접미사)	suffix	order pair
2	aab	(1,1)
0	abaab	(1,2)
3	ab	(1,2)
4	b	(2,0)
1	baab	(2,1)

 

이렇게 얻은 상태를 다시 rank로 바꿔주자. 

 

서로 다른 순서쌍이면 다른 값을 부여하고, 같은 순서쌍이면 같은 값을 부여한다.

 

(1,1)은 1로 부여하고 (1,2)는 2로 부여하고 (2,0)은 3으로 부여하고 (2,1)은 4로 부여하면 될 것이다.

 

어떤 값을 쓸지는 상관없지만 빠른 접미사에는 작은 값으로, 동일한 순서에는 동일한 값으로 부여하는게 중요하다.

 

suffix array(i번째 접미사)	suffix	rank
2	aab	1
0	abaab	2
3	ab	2
4	b	3
1	baab	4

 

 

다음단계는 이전에 d = 2개의 글자를 기준으로 정렬했으므로, 이번엔 2배하여 d = 4개의 글자를 기준으로 정렬한다.

 

각 i번째 접미사의 i + d/2번째 접미사의 rank를 이용하여 순서쌍으로 나타내자.

 

aab의 경우 i + d/2번째 접미사는 2글자 앞으로 간 b이고 이것의 rank는 3이므로 (1,3)으로 나타난다.

 

abaab의 경우 i+d/2번째 접미사는 2글자 앞으로 간 aab이고 이것의 rank는 1이므로 (2,1)로 나타난다.

 

suffix array(i번째 접미사)	suffix	order pair
2	aab	(1,3)
0	abaab	(2,1)
3	ab	(2,0)
4	b	(3,0)
1	baab	(4,2)

 

ab와 b의 경우 2글자 앞으로 간 문자열은 빈 문자열이니 (2,0), (3,0)이 된다.

 

baab는 2글자 앞으로 가면 ab가 되니 (4,2)가 된다.

 

이제 이 순서쌍으로부터 정렬을 수행한다.

 

(1,3), (2,0), (2,1), (3,0), (4,2)가 된다.

 

suffix array(i번째 접미사)	suffix	order pair
2	aab	(1,3)
3	ab	(2,0)
0	abaab	(2,1)
4	b	(3,0)
1	baab	(4,2)

 

다음 단계는 앞에서부터 d = 8글자 기준으로 정렬하는데.. s = abaab의 길이는 5이므로 수행할 필요가 없다.

 

------------------------------------------------------------------------------------------------------------------------------------------

 

이거 반례가 s = zzz이면 [z,zz,zzz]가 나와야하는데 d < n일때 끝내버리면 [z,zzz,zz]나오더라

 

i+d/2번째 접미사가 빈 문자열이 아니라면 계속 수행해줘야한다.

 

d = 8이면 d/2 = 4이므로 i = 0인 경우 여전히 i+d/2번째 접미사가 존재할 수 있다.

 

그러니까 d < 2n일때 반복을 종료하라 이 말이지

 

--------------------------------------------------------------------------------------------------------------------------------------------

 

아무튼 위에 정렬된 상태를 새로운 rank로 바꿔주자

 

모든 순서쌍이 서로 다르니 서로 다른 rank를 부여하면 될 것 같다.

 

suffix array(i번째 접미사)	suffix	rank
2	aab	1
3	ab	2
0	abaab	3
4	b	4
1	baab	5

 

이 상태에서 각각 i + d/2번째 접미사의 rank를 이용해 순서쌍을 구성하자.

 

aab의 경우 4글자 앞은 빈 문자열이니 (1,0)

 

ab의 경우도 (2,0)

 

abaab의 경우는 4글자 앞이 b이므로 b의 rank인 4를 이용해서 (3,4)로 구성

 

b,baab의 경우 4글자 앞이 빈 문자열이니 각각 (4,0), (5,0)

 

suffix array(i번째 접미사)	suffix	order pair
2	aab	(1,0)
3	ab	(2,0)
0	abaab	(3,4)
4	b	(4,0)
1	baab	(5,0)

 

이제 이 상태에서 순서쌍을 정렬하면...

 

(1,0), (2,0), (3,4), (4,0), (5,0)이다. 그리고 새로운 rank로 각각 1,2,3,4,5로 부여하면 되겠지

 

suffix array(i번째 접미사)	suffix	rank
2	aab	1
3	ab	2
0	abaab	3
4	b	4
1	baab	5

 

다음 앞에서부터 d = 16 글자를 기준으로 정렬을 수행한다.

 

하지만 s = abaab의 길이 5의 2배를 넘어섰으므로 더 이상 수행할 필요 없다.

 

즉 i+d/2번째 접미사가 모두 빈 문자열이니 더 이상 의미없다.

 

그러므로 s = abaab의 suffix array는 [2,3,0,4,1]이 된다.

 

참고로 위 과정을 보면 알겠지만, 순서쌍 정렬 후에 새로 부여한 rank가 모두 서로 다르다면, 반복을 멈춰도 된다.

 

새로 부여한 rank는 순서쌍의 첫번째 구성인데, 순서쌍 정렬을 하면 첫번째 원소를 기준으로 정렬하니, 

 

그 뒤로는 정렬하더라도 변화가 없다.

 

위에서 d = 8글자까지 정렬을 수행했지만, 사실 d = 4글자에서 더 이상 정렬하지 않아도 된다는 것을 확인할 수 있다

 

다음은 d = 4인 경우

 

suffix array(i번째 접미사)	suffix	order pair >> rank
2	aab	(1,3) >> 1
3	ab	(2,0) >> 2
0	abaab	(2,1) >> 3
4	b	(3,0) >> 4
1	baab	(4,2) >> 5

 

다음은 d = 8인 경우

 

suffix array(i번째 접미사)	suffix	order pair >> rank
2	aab	(1,0) >> 1
3	ab	(2,0) >> 2
0	abaab	(3,4) >> 3
4	b	(4,0) >> 4
1	baab	(5,0) >> 5

 

5. 구현 예시

 

다음은 위 알고리즘을 파이썬으로 나름대로 구현한 코드

 

1) 3*n의 rank 배열을 초기화

 

2) i가 0부터 n-1까지 순회하여, i번째 접미사의 rank를 부여

 

rank배열의 첫번째 원소는 i번째 접미사의 rank

 

두번째 원소는 0

 

세번째 원소는 i번째 접미사의 시작 위치 i로 초기화

 

3) d = 1로 초기화

 

4) d < 2n일때 다음을 계속 반복

 

4-1) rank배열의 첫번째 원소와 두번째 원소를 기준으로 정렬

 

4-2) 정렬된 rank배열의 새로운 rank를 구한다.

 

new_rank라는 배열로 0~n-1번째 접미사들의 새로운 rank를 저장

 

0번째 접미사 new_rank[0] = 1로 초기화

 

rank배열을 순회해서 i-1번째 rank의 첫번째 원소 두번째 원소와 i번째 rank의 첫번째 원소 두번째 원소가 동일하면

 

동일한 rank를 부여

 

그렇지 않다면, 이전에 저장된 new_rank[i-1]에 1을 더한 값을 new_rank[i]에 저장

 

4-3) 새로운 rank를 바탕으로 rank배열 재구성

 

new_rank[n-1] == n이라는 것은 모든 접미사들의 새로운 rank가 서로 다르다는 뜻으로 접미사 배열이 완성되었으니 반복문 탈출

 

그렇지 않다면, rank배열의 첫번째 원소에 새로운 rank값을 부여

 

ind_rank라는 배열로 i번째 접미사에 부여된 새로운 rank를 저장

 

4-4) rank배열의 두번째 rank인 i+d/2번째 접미사의 rank를 재구성

 

이전에 저장해놓은 ind_rank를 이용해서, i+d/2번째 접미사의 rank를 새롭게 부여

 

(d = 1부터 시작했으므로, d/2는 계산할 필요 없다)

 

 i번째 접미사의 위치는 rank[i][2]에 저장되어 있다.

 

rank[i][2] + d가 index범위인 n-1보다 크면 빈문자열을 부여하기 위해 0을 지정

 

그렇지 않다면 ind_rank에 저장된 값 ind_rank[rank[i][2]+d]를 부여

 

4-5) d를 2배하고 다음 반복문으로 이동

 

4-6) 반복문이 종료되면, rank배열의 세번째 원소에 suffix array값이 저장되어 있다. 

 

일차원 배열에 따로 저장하여 return

 

#suffix array
#Manber-Myers Algorithm(O(nlog^2n))
def get_suffix_array(s):
    
    n = len(s)

    #i+d/2번째 접미사의 rank를 찾다가, 넘어가는 경우 빈 문자열의 rank는 0으로 하기 위해
    rank = [[0,0,0] for _ in range(n)]

    #d = 1일때 정렬단계
    for i in range(n):

        #첫번째 원소는 i번째 접미사의 rank
        #i번째 접미사의 첫 문자를 아스키코드로 바꿔놓은 값으로 바꿔놓는다
        #소문자로만 이루어져있다고 가정

        #두번째 원소는 i+d/2번째 접미사의 rank

        #세번째 원소(suffix array)는 i번째 접미사의 시작 인덱스 i로 초기화
        rank[i] = [ord(s[i]) - ord('a') + 1,0,i]
    
    
    d = 1 #d/2를 나타내는 값
    
    #i + d/2가 모두 빈 문자열이 될때까지 반복문을 수행
    #d < 2*n일때 반복을 종료
    while d < 2*n:
        
        #d단계 정렬 O(NlogN)정렬
        #첫번째, 두번째 원소로만 정렬하도록
        rank = sorted(rank,key = lambda x: [x[0],x[1]])

        #rank 재구성

        new_rank = [0]*n
        new_rank[0] = 1

        for i in range(1,n):
            
            if rank[i-1][0] == rank[i][0] and rank[i-1][1] == rank[i][1]:
                
                new_rank[i] = new_rank[i-1]
            
            else:
                
                new_rank[i] = new_rank[i-1] + 1
        
        #모든 접미사가 1~n개의 그룹으로 나뉘면 접미사 배열이 완성된 것
        #새롭게 부여된 rank는 첫번째 원소를 구성하는데,
        #모두 서로 다르다면 순서쌍을 정렬 하더라도 변화 없기 때문이다.
        if new_rank[n-1] == n:
            
            break
        
        #i번째 접미사의 rank를 저장
        ind_rank = [0]*n

        for i in range(n):
            
            rank[i][0] = new_rank[i]
            ind_rank[rank[i][2]] = rank[i][0]
        

        #순서쌍 재구성
        #두번째 원소를 i+d/2번째 접미사의 rank로 구성
        for i in range(n):
            
            #i번째 접미사의 위치 i = rank[i][2]
            #d/2칸 앞의 위치는 rank[i][2] + d

            #d/2칸 앞 위치가 길이를 넘어가면, 0으로
            if rank[i][2]+d >= n:
                
                rank[i][1] = 0

            #길이를 넘어가지 않으면...
            #i+d/2번째 접미사의 rank는 ind_rank[rank[i][2]+d]에 있다

            else:
                
                rank[i][1] = ind_rank[rank[i][2]+d]

        #다음 d 값을 2배 하기
        d *= 2
    
    #rank배열의 3번째 원소를 가지고와 suffix array 구성
    suffix = [0]*(n)

    for i in range(n):
        
        suffix[i] = rank[i][2]

    return suffix

s = input()

suffix = get_suffix_array(s)

print(suffix)

 

6. Longest Common Prefix

 

Suffix array는 사실 Suffix Tree의 대안으로 나온 자료구조인데, suffix array만으로는 대안이 될 수 없고,

 

추가로 LCP 배열이라고 불리는 Longest Common Prefix를 구해야한다고 한다.

 

suffix tree는 안쓰이는것 같아서.. 지금 굳이 공부하고 싶지는 않고(이걸로도 힘들다)

 

LCP는 접미사 배열 상에서 이웃한 두 접미사 간의 최장 공통 접두사(Longest common prefix)를 저장한 배열이라고 한다

 

그러니까 i번째 접미사와 i-1번째 접미사의 가장 긴 공통 접두사의 길이를 저장한다.

 

(경우에 따라 i번째 접미사와 i+1번째 접미사를 저장하는 경우도 있다)

 

당연히 i = 0인 경우 i-1번째는 정의되지 않으니 lcp[0]는 존재하지 않는다.

 

예를 들어 s = ASDSDASD에 대해 LCP를 구해보자.

 

먼저 suffix array를 구한다. 위에서 구현한 코드로 구해보았다

 

suffix array	suffix	lcp
5	ASD	-
0	ASDSDASD
7	D
4	DASD
2	DSDASD
6	SD
3	SDASD
1	SDSDASD

 

i = 0인 경우 존재하지 않으니 따로 표시해두고, i = 1인 경우 ASD와 ASDSDASD의 최장 공통 접두사는...

 

ASD니까 길이는 3이다. 그래서 lcp[1] = 3

 

i = 2인 경우 ASDSDASD와 D의 최장 공통 접두사는 존재하지 않으므로 lcp[2] = 0

 

---------------------------------------------------------------------------------------------------------------------------------------

 

여기서 D가 될수 있는거 아니냐? 하는데 ASDSDASD의 접두사는..

 

A, AS, ASD, ASDS, ASDSD, ASDSDA, ASDSDAS, ASDSDASD니까 D가 없다..

 

---------------------------------------------------------------------------------------------------------------------------------------

 

i = 3인 경우 D와 DASD의 최장 공통 접두사는 D로 lcp[3] = 1

 

i = 4인 경우 DASD와 DSDASD의 최장 공통 접두사는 D이니 lcp[4] = 1

 

i = 5인 경우 DSDASD와 SD의 최장 공통 접두사는 없으니 lcp[5] = 0

 

i = 6인 경우 SD와 SDASD의 최장 공통 접두사는 SD이므로 lcp[6] = 2

 

i = 7인 경우 SDASD와 SDSDASD의 최장 공통 접두사는 SD이므로 lcp[7] = 2

 

suffix array	suffix	lcp
5	ASD	-
0	ASDSDASD	3
7	D	0
4	DASD	1
2	DSDASD	1
6	SD	0
3	SDASD	2
1	SDSDASD	2

 

접미사 배열을 순회하면서 i, i-1번째 접미사를 잡고, 접두사를 하나하나 비교하며 찾아보면 $O(N^{2})$에 구할 수 있다.

 

당연히 n이 조금만 커도 실전성이 없으니 더 빠른 알고리즘을 원한다..

 

 

7. Kasai 알고리즘 

 

kasai 알고리즘은 "접미사 배열에서 i번째 접미사의 lcp값이 k이면 i+1번째 접미사의 lcp값은 적어도 k-1이다"를 이용하여

 

O(N)에 LCP 배열을 구하는 알고리즘이다.

 

길이가 긴 순서로 LCP를 구한다면 이미 구한 LCP 길이를 이용하여 O(N)에 구할 수 있는데 어떻게 가능할까?

 

먼저 다음과 같이 i = 0번째 접미사의 lcp를 구했다고 한다면..

 

suffix array	suffix	lcp
5	ASD	-
0	ASDSDASD	3

 

여기서 ASD와 ASDSDASD의 첫 글자를 지우면 SD, SDSDASD로 i+1 = 1번째 접미사가 되는데 

 

이러면 원래 LCP의 길이 K = 3에서 접두사 앞의 첫글자 A를 지웠으니 

 

SD,SDSDASD의 LCP는 최소한 2인것을 알 수 있다. 

 

실제로 다음과 같다.

 

6	SD	-
3	SDASD	-
1	SDSDASD	2

 

이런식으로 모든 접미사에 대해 길이 순으로 LCP 길이를 구한다면, 이전에 구한 LCP를 이용해서 O(N)만에 구할 수 있다고 한다.

 

 

8. 구현 예시

 

위 알고리즘을 파이썬으로 나름대로 구현한 예시이다.

 

k가 최대 n번 증가, 최대 n번 감소할 수 있어서 O(N)이라고 하는데..

 

1) i번째 접미사가 suffix array의 어디에 위치하는지를 알아내기 위한 역배열 reverse suffix array를 구한다.

 

i = 0~n-1을 순회하면서

 

reverse_suffix_array[suffix_array[i]] = i로 구할 수 있다.

 

2) k = 0으로 초기화

 

3) i는 0부터 n-1까지 순회하여, i번째 접미사에 대응하는 lcp값을 구한다.

 

i번째 접미사와 인접한 접미사가 ?번째 접미사인지를 구해줘야한다.

 

i번째 접미사는 suffix_array상에 몇번 원소에 있는지 알 수 있다면, 그 번호 -1이 ?값이다.

 

i번째 접미사는 suffix_array상에 reverse_suffix_array[i]번에 존재한다.

 

만약, reverse_suffix_array[i] = 0이라면? lcp[0]는 존재하지 않으므로 continue로 넘어간다.

 

이 단계에서 lcp[0]에 특별한 값을 넣고싶다면 여기서 넣으면 된다.

 

즉, i번째 접미사와 인접한 접미사가 존재하지 않는다.

 

0이 아니라면? i번째 접미사와 인접한 접미사는.. adj = suffix_array[reverse_suffix_array[i]-1]번째 접미사이다. 

 

4) 다음과 같이 문자열 s에서 i+k번, adj+k번부터 시작해서 글자를 하나씩 비교해가며 k값을 증가시킨다

 

서로 글자가 다른 순간, index i+k, adj+k가 n-1을 벗어나는 순간 반복문을 탈출

 

s = ASDSDASD를 생각해보자.

 

i = 0번째 접미사 ASDSDASD와 인접한 접미사는 i = 5번째 접미사 ASD이다.

 

k = 0이고, i + k번째 글자와 adj + k번째 글자를 비교해가며, 일치하면 k를 1 증가시킨다.

 

일치하지 않으면 더이상 최장 공통 접두사가 아니니 반복문을 탈출한다.

 

아래의 경우는 index가 n 이상으로 넘어가니 반복문 탈출

 

 

5) 반복문을 탈출하면 i번째 접미사에 대응하는 lcp값은 k가 된다.

 

i번째 접미사에 대응하는 위치는 reverse_suffix_array[i]이므로, lcp[reverse_suffix_array[i]] = k

 

6) 다음 앞 1글자를 지우고 다음 반복문으로 이동하므로, k가 양수라면 k를 1 감소시킨다.

 

7) 반복문을 탈출하면 얻은 배열이 lcp배열

 

 

#LCP(Longest common prefix) 배열을 구하는 알고리즘

def kasai(suffix_array, s):
    
    n = len(s)

    lcp = [0]*n

    #suffix_array[i] = 사전순으로 i번째 원소가 몇번째 접미사인지.
    #reverse_suffix_array[i] = i번째 접미사가 사전 순으로 몇번째 원소인지

    #suffix_array[k] = i <<>> reverse_suffix_array[i] = k

    #i번째 접미사 suffix_array[k] = i에서 앞 한글자를 지운 
    #i+1번째 접미사 suffix_array[?] = i+1의 ?를 알아야함

    reverse_suffix_array = [0]*n

    for i in range(n):
        
        #suffix_array[i] = k <<<>>> reverse_suffix_array[k] = i
        reverse_suffix_array[suffix_array[i]] = i
    
    #lcp 배열을 구한다

    #가장 긴 접미사인 0번째 접미사부터 시작

    #0번째 접미사는 reverse_suffix_array[0] = i위치에 존재하고
    #0번째 접미사와 인접한 접미사는... suffix_array[i-1] = suffix_array[reverse_suffix_array[0]-1]에 존재
    #두 접미사를 비교해서 몇개가 일치하는지 구한다

    k = 0 #lcp값

    for i in range(n):

        #lcp[0]는 정의하지 않는다
        #suffix_array의 0번째 원소의 접미사는 이전 접미사가 존재하지 않는다
        if reverse_suffix_array[i] == 0: 
            
            k = 0
            continue
        
        #i번째 접미사와 인접한 접미사의 위치
        adj = suffix_array[reverse_suffix_array[i]-1]

        #i번째 접미사와 인접한 접미사의 글자를 하나씩 비교하면서
        #lcp값 k를 1씩 증가시킨다.
        while i+k < n and adj+k < n and s[i+k] == s[adj+k]:
            
            k += 1
        
        #반복문을 탈출하면, i번째 접미사에 대응하는 lcp값은 k가 된다.
        lcp[reverse_suffix_array[i]] = k

        # 그 다음 반복문에서 앞 1글자를 지우므로, lcp는 적어도 1 감소해야한다.
        if k > 0:
            
            k -= 1
    
    return lcp

 

주의할 점은..

 

k = 0에서 다시 증가할수는 없지 않느냐??? 그러니 k = 0이 되는 순간 break하면 되는거 아니냐??

 

그렇지는 않다..

 

아래 표만 보더라도 i = 0에서 lcp = 4로 구하고, i =4에서 lcp = 0으로 구하면..

 

바로 break하면 i = 5, i = 7번째 접미사가 각각 lcp = 1인데 0으로 구해지는 반례가 있다.

 

suffix array	suffix	lcp
10	a	-
7	abra	1
0	abracadabra	4
3	acadabra	1
5	adabra	1
8	bra	0
1	bracadabra	3
4	cadabra	0
6	dabra	0
9	ra	0
2	racadabra	2

 

 

9. 연습문제

 

9248번: Suffix Array (acmicpc.net)

9248번: Suffix Array

 

시작 인덱스가 zero index가 아니라 one index라는 점만 주의해서 살짝만 바꿔주면 된다.

 

pypy3로 $O(Nlog^{2}N)$은 6초정도에 통과하네