POJ2774(后缀数组 求两串最长公共子串）

后缀数组题集参考来自博客：博客

题目链接

Long Long Message

题意：给你两个字符串，求这两个字符串最长的公共子串

做法：后缀数组，构建sa数组 O(nlogn), 构建 height 数组 O(nlog(n))

我们可以把两个串用一个特殊字符拼接，然后跑SA求出height，由于最长公共子串肯定是height中的某一个，而且要满足sa[i]和sa[i−1]分别属于两个串，所以只要跑一遍后缀数组遍历一遍height就好了。

#include<cstdio>
#include<cstring>
#include<iostream>
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\n", 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<<s+1<<endl;
        //for(int i=1;i<=n;++i) printf(" n:%d sa:%d %d\n", n, sa[i], height[i]);

        int ans = 0;
        for(int i=2;i<=n;++i){
            if(height[i] > 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\n", ans);
    }
}
/*
aba
aba
*/