POJ 2774(接尾辞配列は2列の最も長い共通のサブ列を求めます)

接尾辞配列問題セットリファレンスブログ:ブログ

タイトルリンク

Long Long Message

題意:あなたに2つの文字列をあげて、この2つの文字列の最も長い共通のサブストリングを求めます
作り方:接尾辞配列、sa配列O(nlogn)、height配列O(nlog(n))
2つの列を1つの特殊な文字でつなぎ、SAを走ってheightを求めることができます.最長の共通サブ列はheightのいずれかに違いありません.sa[i]とsa[i−1]がそれぞれ2つの列に属していることを満たすため、接尾辞配列を走ってheightを遍歴すればいいのです.

#include
#include
#include
const int N=1e6+10;
using namespace std;
char s[N], s1[N], s2[N];
int y[N],x[N],c[N],sa[N],rk[N],height[N];
int n, m, len1, len2;

void get_SA() {
    for(int i=0;i<=n;++i){
        c[i]=x[i]=y[i]=sa[i]=rk[i]=height[i]=0;
    }
    int m = 122; //ascll('z')=122
    for(int i=0;i<=m;++i) c[i] = 0;
	for (int i=1; i<=n; ++i) ++c[x[i]=s[i]];// 
	for (int i=2; i<=m; ++i) c[i]+=c[i-1];// 
	for (int i=n; i>=1; --i) sa[c[x[i]]--]=i;//   sa
	for (int k=1; k<=n; k<<=1){ // 
		int num=0;
		for (int i=n-k+1; i<=n; ++i) y[++num]=i;// ， 
		for (int i=1; i<=n; ++i) if (sa[i]>k) y[++num]=sa[i]-k;

		for (int i=1; i<=m; ++i) c[i]=0;       // 
		for (int i=1; i<=n; ++i) ++c[x[i]];    // 
		for (int i=2; i<=m; ++i) c[i]+=c[i-1]; // 
		for (int i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0;// 

		for(int i=1;i<=n;++i) y[i] = x[i];
		x[sa[1]] = num = 1;
		for (int i=2; i<=n; ++i) // x 
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;

		if (num==n) break;
		m=num;
	}
	//for (int i=1; i<=n; ++i) printf("%d ", sa[i]);
}

void get_height() {
	int k=0;
	for (int i=1; i<=n; ++i) rk[sa[i]]=i;
	for (int i=1; i<=n; ++i){
		if (rk[i]==1) continue;// height 0
		if (k) --k;   //h[i]>=h[i-1]-1;
		int j=sa[rk[i]-1];
		while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
		height[rk[i]]=k;//h[i]=height[rk[i]];
	}
//	puts("");
//	for(int i = 1; i <= n; ++i) printf("%d ",height[i]);
}

int main() {
    while(~scanf("%s%s", s1+1, s2+1))
    {
        len1 = strlen(s1+1);
        len2 = strlen(s2+1);
        //printf("len1:%d len2:%d
", len1, len2);
        n = 0;
        for(int i=1;i<=len1;++i) s[++n] = s1[i];
        s[++n]='*';
        int now = n;
        for(int i=1;i<=len2;++i) s[++n] = s2[i];
        s[n+1] = 0;
        get_SA();
        get_height();
        //cout< ans){
                if(sa[i-1] < now && sa[i] > now) ans = max(ans, height[i]);
                if(sa[i] < now && sa[i-1] > now) ans = max(ans, height[i]);
            }
        }
        printf("%d
", ans);
    }
}
/*
aba
aba
*/