[Algorithm] LCP 배열(Longest Common Prefix Array)

이번에는 LCP 배열에 대해 알아보자! LCP 배열을 이해하기 위해서는 이전에 쓴 글인 접미사 배열을 우선적으로 이해해야한다. 

 

2023.03.27 - [Algorithm] - [Algorithm] 맨버-마이어스 알고리즘(Suffix Array)

[Algorithm] 맨버-마이어스 알고리즘(Suffix Array)

 

위의 글에서 들었던 예시인 banana를 사용하자. LCP 배열을 만들기 위해서는 우선 해당 접미사가 정렬된 Suffix 배열에서 어느 위치에 있는지를 기록해야한다. 이를 위해 배열을 하나 더 추가하자. 

 

위의 표에서 suffix는 좀 더 수월한 이해를 위해 추가했다. 실제로 배열은 idx와 pos_in_suffixes 값만을 갖는다. 여기서 pos_in_suffixes는 해당 접미사가 정렬된 접미사 배열 안에서 몇번째 인덱스에 위치하는지를 나타낸다. 

 

이제 첫번째 접미사인 banana부터 검사를 진행한다.

 

위의 표를 보면, banana의 접미사 배열 안에서의 위치가 3인 것을 알 수 있다. 이제 접미사 배열 안에서 banana의 바로 앞에 있는 문자와 비교를 진행하는데, 그렇게되면 2번 인덱스에 있는 anana와 비교를 진행하게 될 것이다. 비교를 진행하기 전에 banana와 anana의 겹치는 문자의 개수를 저장할 변수 k를 0으로 초기화시켜주고 시작한다.

하지만 banana와 anana는 첫번째 문자부터 다르기때문에 lcp[0]의 값은 0으로 초기화되고 검사가 끝날 것이다. 

이제 두번째 문자인 anana에 대해 검사를 진행해보자. 

이 경우에는 두 문자가 앞에서부터 총 세개의 문자가 겹치게된다. 따라서 lcp[1] = 3으로 초기화가 될 것이다. 이때 앞에서 선언했던 k값도 같은 문자가 나올때마다 1씩 증가하게 되어 3인 상태로 끝나게 된다. 

 

여기에서 다음에 비교할 문자는 nana가 될 것인데, 이번에 검사한 anana와 nana는 맨 앞에 접미사의 차이만 존재한다. 이때 anana의 lcp 값이 3으로 끝났으므로, nana 또한 lcp 값이 최소한 2는 나올 것임을 보장할 수 있다. 따라서 nana를 검사할때는 k값이 이전 anana의 k값이었던 3에서 1을 감소시킨 2에서 시작하게된다. 

이제 na와 nana를 비교하게된다. k값이 2부터 시작하므로 각각의 세번째 문자부터 비교하게되는데, 세번째 문자는 겹치지 않기때문에 lcp[2] = 2로 설정되고 k값은 증가하지않고 1이 감소된다. 

 

이후 위의 과정을 반복하면 lcp 배열은 다음과 같이 완성된다. 

이렇게 k값을 매번 0부터 시작하지않고, 이전 문자를 검사할때 설정한 k값을 활용함으로써 $O(n)$의 시간복잡도로 LCP 배열을 계산할 수 있다. 위의 과정을 코드로 구현하면 아래와 같다. 

 

def make_lcp(pos, suffixes, text):
    n = len(text)
    lcp = [0] * len(suffixes)

    k = 0
    for i in range(n):
        if pos[i]:
            j = suffixes[pos[i]-1]
            while i+k < n and j+k < n and text[i+k] == text[j+k]:
                k += 1
            lcp[pos[i]] = k

            if k:
                k -= 1

    return lcp