LCP 알고리즘(Longest Common Prefix)

LCP (Longest Common Prefix) 알고리즘이란?

LCP는 두 접미사의 최대 공통 접두사의 길이를 의미한다.

LCP를 이해하기 위해서는 아래 링크의 내용을 이해하여야 한다.

물론 LCP를 공부하기 위해 찾아온 사람들은 아래 내용을 알고 왔으리라 생각한다.

Suffix Array를 구하는 게시물 :: http://programbasic.tistory.com/613

위의 게시물에서 banana로 구한 테이블을 정리해보자.

i	SA[i]	Suffix	LCP[i]
0	5	a
1	3	ana
2	1	anana
3	0	banana
4	4	na
5	2	nana

여기서 두 접미사의 최대 공통 접두사의 길이를 직접 구해보면

i = 0일때 a 이전의 값은 없으므로 x가 된다.

i = 1일때 a와 ana의 최대 공통 접두사 길이(LCP)는 1이다

i = 2일때 ana와 anana의 LCP는 3이다.

i = 3일때 anana와 banana의 LCP는 0이다.

i = 4일때 banana와 na의 LCP는 0이다.

i = 5일때 na와 nana의 LCP는 2이다.

따라서 LCP 테이블은 다음과 같이 완성된다.

i	SA[i] (= Pos[i])	Suffix	LCP[i]
0	5	a	x
1	3	ana	1
2	1	anana	3
3	0	banana	0
4	4	na	0
5	2	nana	2

이렇게 두 단어를 가지고 직접 비교하면 의 시간이 걸린다.

따라서 아래의 사실과 명제를 통해 O(N)에 해결하는 알고리즘을 알아보고자 한다.

우선 아래 나와있는 단어에 대해서 설명을 하자면

lcp(x,y)는 문자열 S에 대해 S[x...]와 S[y...]의 최대 공통 접두사의 길이로 정의한다.

Pos[]는 문자열 S의 접미사 배열로 정의한다.(위의 SA[]와 동일하다.)

Rank[i]는 S[i...]가 사전순으로 몇 번째 접미사인지 들어있다. 결국 Rank[pos[i]] = i이다.

다시말해 Pos[1] = 3인데 Rank[3] = 1인 관계이다. (역함수 관계)

---

햇갈리지 않게 미리 정리를 해 두자면

S[0...] = "banana"

S[1...] = "anana"

S[2...] = "nana"

S[3...] = "ana"

S[4...] = "na"

S[5...] = "a" 이고,

Rank[0] = 3

Rank[1] = 2

Rank[2] = 5

Rank[3] = 1

Rank[4] = 4

Rank[5] = 0 이다.

---

접미사 배열에서 이웃한 두 접미사의 lcp가 이웃하지 않고 떨어져 있는 lcp보다 크거나 같다는 뜻이다.

예를 들어 x가 1, y가 2, z가 3라 생각해보자.

lcp(Pos[1], pos[2]) >= lcp(Pos[1], Pos[3])의 의미는 lcp(3, 1) >= lcp(3, 0)

즉, S[3...]와 S[1...]의 최대 공통 접두사는 3이고, S[3...]와 S[0...]의 최대 공통 접두사 0이다.

따라서 3 >= 0을 만족하게 된다.

결국 사전 순으로 정렬되어있는 SA는 이웃할 때 겹치는 부분이 많고, 이웃하지 않을 때는 겹치는 부분이

이웃할 때 보다는 무조건 작거나 같다는 의미이다. 

이웃한 접미사 배열(S[Pos[x-1]...]와 S[Pos[x]...])의 최대 공통 접두사가 1보다 크면(첫 글자가 같으면), 

Rank[Pos[x-1]+1] < Rank[Pos[x]+1] 이어야 한다.

즉 x = 2일때 보면 S[Pos[1]...]와 S[Pos[2]...] 즉, S[3...]와 S[1...]는 lcp가 3이니

if( 3 > 1 )을 만족한다.

이때 Rank[Pos[1]+1] < Rank[Pos[2]+1] -> Rank[3+1] < Rank[1+1] -> Rank[4] < Rank[2] 

따라서 4 < 5이라는 의미이다.

이웃한 접미사 배열의 최대 공통 접두사가 1보다 크면, lcp(Pos[x-1]+1, Pos[x]+1) = lcp(Pos[x-1], Pos[x])-1이다.

x = 2일때 보면 lcp(Pos[1]+1, Pos[2]+1) = lcp(Pos[1], Pos2]) - 1인데, 

lcp(3+1, 1+1) = lcp(3,1) - 1 -> lcp(4, 2) = lcp(3, 1) - 1 -> 2 = 2를 만족한다.

즉, 이웃한 접미사 배열의 첫 글자가 같기 때문에 첫 글자를 뺀 길이 또한 같다는 의미이다.

이러한 사실들을 기반하여 LCP Array 소스 코드를 구현하면 다음과 같다.

 

    // RANK 배열에는 접미사 배열 순서가 들어간다.

    for (int i = 0; i < n; i++)

        RANK[SA[i]] = i;

 

    int len = 0;

 

    for (int i = 0; i < n; i++)

    {

        int k = RANK[i];

        if (k)

        {

            int j = SA[k - 1];

 

            while (str[j + len] == str[i + len])

                len++;

 

            LCP[k] = len;

 

            if (len)

                len--;

        }

    }

 

아래는 특정 문자열을 입력하였을 때, Suffix가 사전순으로 정렬된 모습, Suffix Array, LCP가 나타난다.

소스 코드

#include <cstdio>
#include <algorithm>
#include <cstring>
 
#define MAX_N 600000
 
using namespace std;
 
char str[MAX_N];
int t, n, g[MAX_N], tg[MAX_N], SA[MAX_N], RANK[MAX_N], LCP[MAX_N];
 
bool cmp(int x, int y)
{
    // 현재 보고있는 단어가 같으면 t번째 기준으로 정렬
    if (g[x] == g[y])
        return g[x + t] < g[y + t];
 
    // 현재 보고있는 단어가 다르다면 바로 정렬
    return g[x] < g[y];
}
void getSA(const char* str)
{
    t = 1;
    n = (int)strlen(str);    //글자의 수 배정
 
    //첫 글자에 의한 그룹을 정해주는 전처리
    for (int i = 0; i < n; i++)
    {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }
 
    //1,2,4,8... 씩 단어의 길이보다 작은 경우를 탐색
    while (t <= n)
    {
        //    g[n] = -1;
        sort(SA, SA + n, cmp);    //그룹에 의한 정렬
        tg[SA[0]] = 0;    //다음 그룹을 할당하기 위하여 tempgroup의 첫번째 번호 배정
 
        //다음 그룹 배정 
        for (int i = 1; i < n; i++)
        {
            //그룹이 다를 경우 다음 그룹 번호 할당
            if (cmp(SA[i - 1], SA[i]))
                tg[SA[i]] = tg[SA[i - 1]] + 1;
 
            //그룹이 같을 경우 같은 그룹 번호 할당
            else
                tg[SA[i]] = tg[SA[i - 1]];
        }
 
        //새로운 그룹 할당
        for (int i = 0; i < n; i++)
            g[i] = tg[i];
 
        t <<= 1; // t *= 2;
    }
}
int main()
{
    scanf("%s", &str);
    getSA(str);
 
    // RANK 배열에는 접미사 배열 순서가 들어간다.
    for (int i = 0; i < n; i++)
        RANK[SA[i]] = i;
 
    int len = 0;
 
    for (int i = 0; i < n; i++)
    {
        int k = RANK[i];
        if (k)
        {
            int j = SA[k - 1];
 
            while (str[j + len] == str[i + len])
                len++;
 
            LCP[k] = len;
 
            if (len)
                len--;
        }
    }
 
    printf("\n[Suffix Array]\n");
 
    for (int i = 0; i < n; i++)
        printf("%s\n", str + SA[i]);
 
    printf("\n[Suffix Array Order]\n");
    for (int i = 0; i < n; i++)
        printf("%d ", SA[i] + 1);
 
    printf("\n\n[LCP]\n");
    for (int i = 0; i < n; i++)
    {
        if (!i)
            printf("x ");
        else
            printf("%d ", LCP[i]);
    }
 
    printf("\n\n");
 
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>