记录编号	587756	评测结果	AAAAAAAAAA
题目名称	最长公共子串	最终得分	100
用户昵称	wow草原	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2024-04-25 20:29:30	内存使用	0.59 MiB

#include<bits/stdc++.h>
using namespace std;
int sa[10010],rk[10010],hi[10010],k,rk2[10010],n,n1,n2,h,maxx;
char s[10010],s1[5010],s2[5010];
bool cmp(int i,int j){
    if(rk[i]!=rk[j])
    return rk[i]<rk[j];
    int ri=-1,rj=-1;
    ri=rk[i+k];
    rj=rk[j+k];
    return ri<rj;
}

int main(){
    freopen("lcsubstr.in","r",stdin);
    freopen("lcsubstr.out","w",stdout);
    scanf("%s%s", s1 + 1,s2 + 1);
    n1=strlen(s1 + 1),n2=strlen(s2+1);
    for(int i=1;i<=n1;i++)
    s[i]=s1[i];
    s[n1+1]='0';
    for(int i=1;i<=n2;i++)
    s[n1+1+i]=s2[i];
    n=n1+n2+1;
    for(int i=1;i<=n;i++)
    sa[i]=i,rk[i]=s[i];
    for(k=1;k<=n;k*=2){
        sort(sa+1,sa+1+n,cmp);
        rk2[sa[1]]=1;
        for(int i=2;i<=n;i++)
        rk2[sa[i]]=rk2[sa[i-1]]+cmp(sa[i-1],sa[i]);
        for(int i=1;i<=n;i++)
        rk[i]=rk2[i];
    }
    hi[1]=0;
    h=0;
    for(int i=1;i<=n;i++){
        int j=sa[rk[i]-1];
        if(h>0)
        h--;
        for(;j+h<=n&&i+h<=n;h++)
        if(s[j+h]!=s[i+h])
        break;
        hi[rk[i]]=h;
    }
    cout<<endl;
    for(int i=1;i<n;i++){
        int x=sa[i-1],y=sa[i];
        if(min(x,y)<n1&&max(x,y)>n1) {
            maxx=max(hi[i],maxx);
        }
    }
    cout<<maxx;
    return 0;
}