SP1812 LCS2 - Longest Common Substring II 题解

· · 题解

比较套路的题，其实二分完全是可以的，卡卡常跑得飞快。

首先拼接成一个字符串，中间放特殊符号是显然的。

套路是二分，然后变成判断是否存在满足条件的长度为 k 的子串。

由于需要满足长度为 k，我们就可以以 height 的值将后缀分组，如果存在 height(i)<k 就断开，i 往后作为一个新的组。

这样可以保证组内任意两个后缀的最长公共前缀长度至少为 k，所以我们考虑是否存在组满足条件即可，对于这题，我们只需要保证每个字符串都有对应的后缀在组内。

时间复杂度为 \mathcal O(n\log n)。

#include<bits/stdc++.h>
#define LL int
using namespace std;
const LL N=2e6+5;
LL T,n,L[N],R[N],sa[N],rk[N],h[N],b[N],tmp[N],tmp2[N],m=200,hav[12];
char s[N],a[N];
bool pd(LL x)
{
    for(int i=1;i<=n;i++)
    {
        if(h[i]<x)
        {
            LL flg=1;
            for(int j=1;j<=T;j++)
            {
                if(!hav[j])
                {
                    flg=0;
                    break;
                }
            }for(int i=1;i<=T;i++)hav[i]=0;
            if(flg)return 1;

        }
        for(int j=1;j<=T;j++)
        {
            if(L[j]<=sa[i]&&sa[i]<=R[j])
            {
                hav[j]=1;
                break;
            }           
        }
    }
    LL flg=1;
    for(int j=1;j<=T;j++)
    {
        if(!hav[j])
        {
            flg=0;
            break;
        }
    }for(int i=1;i<=T;i++)hav[i]=0;
    if(flg)return 1;

    return 0;
}
int main()
{

    while(~scanf("%s",s+1))
    {

        L[++T]=n+1,R[T]=n+strlen(s+1);
        for(int j=L[T];j<=R[T];j++)a[j]=s[j-L[T]+1];
        n=R[T]+1;
        a[n]='#'+T-1;
    }
    for(int i=1;i<=n;i++)b[rk[i]=a[i]]++;
    for(int i=1;i<=m;i++)b[i]+=b[i-1];
    for(int i=n;i>=1;i--)sa[b[rk[i]]--]=i;
    LL t=0;
    for(int i=1;i<=n;i++)tmp[i]=rk[i];
    for(int i=1;i<=n;i++)
    {
        if(tmp[sa[i]]==tmp[sa[i-1]])rk[sa[i]]=t;
        else rk[sa[i]]=++t;
    }
    m=t;
    for(LL l=1;l<n;l<<=1)
    {
        LL t=0;
        for(int i=n-l+1;i<=n;i++)tmp[++t]=i;
        for(int i=1;i<=n;i++)if(sa[i]>l)tmp[++t]=sa[i]-l;
        for(int i=1;i<=m;i++)b[i]=0;
        for(int i=1;i<=n;i++)++b[tmp2[i]=rk[tmp[i]]];
        for(int i=1;i<=m;i++)b[i]+=b[i-1];
        for(int i=n;i>=1;i--)sa[b[tmp2[i]]--]=tmp[i];
        for(int i=1;i<=n;i++)tmp[i]=rk[i];
        t=0;
        for(int i=1;i<=n;i++)
        {
            if(tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+l]==tmp[sa[i-1]+l])rk[sa[i]]=t;
            else rk[sa[i]]=++t;
        }

        m=t;
        if(m==n)break;
    }
    t=0;
    for(int i=1;i<=n;i++)
    {
        if(rk[i]==1)continue;
        if(t)t--;
        while(a[i+t]==a[sa[rk[i]-1]+t])t++;
        h[rk[i]]=t;

    }
    LL l=1,r=n,ans=0;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        if(pd(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d",ans);
}