접미사 배열, LCP

아래 소스코드는 접미사 배열을 구하는 함수.

어떤 문자열의 모든 접미사를 사전순으로 정렬해둔것.

출처 : http://blog.myungwoo.kr/57

사진 뜻. 

0번째 접미사 배열은 아래 문자열 banana의 5번째부터 끝까지다. == a

1번째 접미사 배열은 아래 문자열 banana의 3번째부터 끝까지다. == ana

2 : anana, 3 : banana, 4 : na, 5 : nana

*같은 문자로 시작하는 접미사 배열은 인접해 있음. a로 시작하는 접미사배열은 0,1,2의 경우.

b로 시작하는 접미사배열은 3, n은 4,5에 있다.

LCP 란 i번째 접미사와 i-1번째 접미사의 '가장 긴 공통 접두사의 길이'라고 한다.

ex) i번째 접미사 : a, i+1번째 접미사 : ana라고 하면 lcp는 1.

ana, anana의 lcp는 3(ana의 3). anana와 banana는 0이다. 앞에서 시작하는게 a와 b로 다르기 때문.

이런식. 종만북소스.

#include<list>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include <algorithm>

using namespace std;


vector<int> getSuffixArray(const string& s)
{
	int n=s.size();
	int t=1;
	vector<int> group(n+1);
	for(int i=0;i<n;i++) group[i]=s[i];
	group[n] = -1;
	vector<int> suffix(n);
	for(int i=0;i<n;i++) 
		suffix[i] = i;
	while(t<n)
	{
		auto cmp = [&group, t](int a, int b)
		{
			if(group[a] != group[b])
				return group[a] < group[b];
			return group[a+t] < group[b+t];
		};
	
		sort(suffix.begin(), suffix.end(), cmp);
		t *= 2;
		if(t>=n) break;

		vector<int> newGroup(n+1);
		newGroup[n] = -1;
		newGroup[suffix[0]]=0;
		for(int i=1;i<n;i++)
		{
			if(cmp(suffix[i-1],suffix[i]))
				newGroup[suffix[i]]=newGroup[suffix[i-1]]+1;
			else
				newGroup[suffix[i]]=newGroup[suffix[i-1]];
		}
		group = newGroup;
	}
	return suffix;
}

int commonPrefix(const string &s, int i, int j)
{
	int k=0;
	while(i<s.size() && j<s.size() && s[i]==s[j])
	{
		i++; j++; k++;
	}
	return k;
}

int countSubstrings(const string& s)
{
	vector<int> a = getSuffixArray(s);
	int ret = 0;
	int n = s.size();
	for(int i=0;i<a.size();i++)
	{
		int cp = 0;
		if(i>0) cp = commonPrefix(s,a[i-1],a[i]);
		if(cp > ret)
			ret = cp;
		cout<<"lcp = "<<cp<<endl;
		//ret += s.size() - a[i] - cp;
	}
	return ret;
}

int main()
{
	string a;
	cin>>a;
	vector<int> suffix = getSuffixArray(a);
	for(int i=0;i<suffix.size();i++)
		cout<<i<<" = "<<suffix[i]<<endl;
	cout<<countSubstrings(a)<<endl;
	return 0;
}

위에 적은 블로그에서 가져온 소스. 더 빠르다. 참고용

#include<list>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 500005
  
int N,SA[MAXN],lcp[MAXN];
char S[MAXN];
 
void SuffixArray()
{
    int i,j,k;
    int m = 27; 
    vector <int> cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0);
    for (i=1;i<=N;i++) 
	{
		if(S[i]=='$')
			cnt[x[i] = m]++;
		else
			cnt[x[i] = S[i]-'A'+1]++;
	}
    for (i=1;i<=m;i++) 
        cnt[i] += cnt[i-1];
    for (i=N;i;i--) 
        SA[cnt[x[i]]--] = i;
    for (int len=1,p=1;p<N;len<<=1,m=p)
    {
        for (p=0,i=N-len;++i<=N;) y[++p] = i;
        for (i=1;i<=N;i++) 
            if (SA[i] > len) 
                y[++p] = SA[i]-len;
        for (i=0;i<=m;i++) 
            cnt[i] = 0;
        for (i=1;i<=N;i++) 
            cnt[x[y[i]]]++;
        for (i=1;i<=m;i++) 
            cnt[i] += cnt[i-1];
        for (i=N;i;i--) 
            SA[cnt[x[y[i]]]--] = y[i];
        swap(x,y); p = 1; x[SA[1]] = 1;
        for (i=1;i<N;i++)
            x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p;
    }
}
 
void LCP()
{
    int i,j,k=0;
    vector <int> rank(N+1,0);
    for (i=1;i<=N;i++) 
        rank[SA[i]] = i;
    for (i=1;i<=N;lcp[rank[i++]]=k)
        for (k?k--:0,j=SA[rank[i]-1];S[i+k]==S[j+k];k++);
}


int main()
{
    int i,max=-1;
    scanf("%s",S+1);
	//S[strlen(S+1)+1]='$';
	scanf("%s",S+1+strlen(S+1));

    N = strlen(S+1);
	cout<<"str = "<<S+1<<endl<<"suffix = ";
    SuffixArray(); 
	for(int i=1;i<=N;i++)
		cout<<SA[i]<<" ";
	cout<<endl<<"lcp = ";

    LCP();
    for (i=1;i<=N;i++) 
	{
		cout<<lcp[i]<<" ";
		if(lcp[i]>max)
			max=lcp[i];
	}
    cout<<endl<<max<<endl;
    return 0;
}