문자열 처리 알고리즘 - LCP

LCP (Longest Common Prefix)

문자열이 하나만 주어졌을때 공통된 문자열(substring; subsequence가 아님)의 최대 길이가 얼마인지 구해야 하는 문제가 주어졌다고 하자.

이 때 이 문자열에 대한 Suffix Array를 구해놨다면 O(N)에 문제에 대한 답을 구할 수 있다.  

그럼 이 부분을 KMP로 구할 수 있을까?

안된다. Needle에 대한 스트링이 O(N^2)개 만큼 존재하는데, 이걸 모두 비교하려면 O(N^3)이 걸릴 것이다. 

그래서 나온 방법이 SA를 구한 상태에서 LCP를 O(N)에 구하는 방법이다.

(이전에 내가 올린 포스팅에서 Suffix Array를 O(NlogN)에 구할 수 있는 방법만 소개하였으나 O(N)에 구할 수도 있다.

그러면 SA구하고 LCP까지 다 구해도 O(N) 안에 모두 처리될 것이다.

다만 이 방법은 ps를 할 때 직접 코딩하기에는 무리가 있기도 하고, 나도 모르고... 그래서 안썼다. ^-^''

사실 suffix array는 그 자체만으로 할 수 있는 기능은 거의 없고, 바로 이 LCP를 구하기 위한 전처리 단계와 다를 게 없다고 한다.

아무튼 서론은 이쯤하고,

바로 mississipi의 LCP를 구해보자.

lcp[i]는 i번째 Suffix Array(이하 SA로 기재)와 i-1번째 SA를 비교했을때 겹치는 prefix의 길이를 의미한다.

mississipi를 suffix 순서대로 나열해보면,

i

ipi

issipi

ississipi

mississipi

pi

sipi

sissipi

ssipi

ssissipi

인데,

이를 lcp배열로 나타내면 0 1 1 4 0 0 0 2 1 3 이다.

처음 숫자가 0인 이유는 아무것도 없는 문자와 i를 비교해서 0이고

그 다음 부터는 (i, ipi), (ipi, issipi), (issipi, ississipi), ...  이런 순서로 비교했을때 가장 긴 공통 prefix의 길이(겹치는 prefix의 길이)를 의미한다.

이는 SA를 구한다음 LCP를 구한다는 것을 의미한다.

여기서 SA를 구한다음 LCP를 무식하게 구한다면,

O(N^2)에 구할 수 있는데 N개의 SA 전부를 문자 하나하나씩 비교하면 된다.

그럼 O(N)에는 어떻게 구할 수 있을까?

원리는 다음과 같다.

issipi

ississipi

를 보자.

공통 된 부분을 굵게 표시해보면 아래와 같다.

issipi

ississipi

그럼 여기서 맨 앞의 i만 빼보자

ssipi

ssissipi

!!!!!!!!!!!!!!!!!

느낌이 팍 오지 않는가?!

lcp값이 4인 두 SA에서 공통된 부분 하나를 빼줬더니 lcp값이 3인 두 SA가 나왔다.

근데 여기서 공통된 부분을 앞에서 하나 빼줬다는건 원래의 문자열 s에서 바로 다음 인덱스를 의미하는 것과 같다.

그니까 mississipi에서 issipi에 해당 되는 부분에서 다시 ssipi를 해당되는 부분을 보면 그냥 바로 다음 인덱스인 것이다.

그래서 SA 2개를 갖다놓고 처음부터 서로 비교해볼 필요 없이 공통된 부분에서 하나씩 빼가면서 너네는 공통된 부분이 "몇개닷~!" 이렇게 바로바로 지정해 주는 방식인 것이다.

크.......

여기까지 봤으면 다 끝난거다.

나머지는 코드보면 이해가 될 것이라 생각한다.

덧붙이자면, LCP를 SA에서부터 선형 시간에 구하는 알고리즘은 서울대 교수님이 일본쪽과 공동으로 연구해서 논문 발표를 했다고 한다.

해당 논문: Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications 

//Suffix Array: O(NlogN), LCP: O(N)    made by plzrun.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#define CHARNUM 256
using namespace std;
vector<int> sfx,g,ng,cnt,orderToIdx;
vector<int> lcp, prevsfx, plcp;
////get Suffix Array O(NlogN) using counting sort.
vector<int> getsfx(const string &s) {
    const int n = s.size();
    int lim = max(n+1, CHARNUM+1);
    sfx.clear(); g.clear(); ng.clear(); orderToIdx.clear();
    sfx.resize(n), g.resize(n+1), ng.resize(n+1), orderToIdx.resize(n+1,0);
 
    for(int i=0; i<n; i++) sfx[i]=i, g[i]=s[i];
 
    for(int t=1; t<n; t<<=1) {
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[min(i+t,n)]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) orderToIdx[--cnt[g[min(i+t,n)]]]=i;
 
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[i]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) sfx[--cnt[g[orderToIdx[i]]]]=orderToIdx[i];
 
        auto cmp = [&](int i, int j)->bool{
            if(g[i]==g[j]) return g[i+t]<g[j+t];
            else return g[i]<g[j];
        };
 
        ng[sfx[0]]=1;
        for(int i=1; i<n; i++) {
            if(cmp(sfx[i-1],sfx[i])) ng[sfx[i]]=ng[sfx[i-1]]+1;
            else ng[sfx[i]]=ng[sfx[i-1]];
        }
        g=ng;
    }
 
    //get LCP O(N)
    lcp.clear(); prevsfx.clear(); plcp.clear();
    lcp.resize(n); prevsfx.resize(n+1); plcp.resize(n+1);
 
    prevsfx[sfx[0]]=-1;
    for(int i=1; i<n; i++) prevsfx[sfx[i]]=sfx[i-1];
    for(int i=0, common=0; i<n; i++) {
        if(prevsfx[i]==-1) plcp[i]=0;
        else {
            while(s[i+common] == s[prevsfx[i] + common]) common++;
            plcp[i]=common;
            common = max(common-1,0);
        }
    }
    for(int i=0; i<n; i++) lcp[i]=plcp[sfx[i]];
 
    return sfx;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    vector<int> sfx = getsfx(s);
 
    printf("sfx: ");
    for(auto &p : sfx) printf("%d ", p);
    puts("");
 
    printf("lcp: ");
    for(auto &p : lcp) printf("%d ", p);
    puts("");
 
    return 0;
}