后缀数组之寻找最大相同子串 poj3216

浅浅的花香味﹌ 2021-11-16 13:48 282阅读 0赞

题意：给一个串，求出最长的那个相同的子串

这个题使用后缀自动机是，首先给每个节点siz赋值为1 ，然后遍历，更新最大的长度。如果有某个串的个数不为1 ，就更新长度，

使用后缀数组是：求出height，然后对答案二分，枚举答案，在判断答案是否满足条件

后缀数组代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int M=100050;
    int d[M],x[M],y[M],sa[M],height[M],rk[M],n,k,m,b[M],c[M];
    void  get_sa() {
        for (int i=1; i<=n; ++i) ++c[x[i]=d[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;
        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]; //第一关键字排名为1~i的数有多少个
            for (int i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y);
            x[sa[1]]=1;
            num=1;
            for (int i=2; i<=n; ++i)
            	if((y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]))x[sa[i]]=num;
            	else x[sa[i]]=++num; 
            if (num==n) break;
            m=num;
        }
        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 && d[i+k]==d[j+k]) ++k;
            height[rk[i]]=k;
        }
    }
    bool judge(int x){
    	int i=2,num;
    	while(1){
    		while(i<=n&&height[i]<x)i++;
    		if(i>n)break;
    		num=0;
    		while(height[i]>=x&&i<=n){num++;i++;}
    		if(num+1>=k){
    			return true;
    		}
    	}
    	return false;
    }
    int main(){ 
    	while(scanf("%d%d",&n,&k)!=EOF){ 
    		for(int i=1;i<=n;i++)scanf("%d",&d[i]),b[i]=d[i];
    		sort(b,b+n+1);
    		m=unique(b+1,(b+n+1))-(b+1);
    		for(int i=1;i<=n;i++)d[i]=lower_bound(b+1,b+m+1,d[i])-(b);
    		get_sa(); //sa数组正确
    		int ans=0,l=1,r=n,mid;
    		while(l<=r){
    			mid=(l+r)>>1;
    			if(judge(mid)){
    				l=mid+1;
    				ans=mid;
    			}else{
    				r=mid-1;
    			}
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }