重复旋律3

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int Rank[maxn],cntA[maxn],cntB[maxn],A[maxn],B[maxn];

int sa[maxn],tsa[maxn],ht[maxn];

int ans,N,ch[maxn];

char str1[maxn],str2[maxn];

void solve()

{

    int i,j;

    for(i=;i<=N;i++)  cntA[i]=;

    for(i=;i<=N;i++)  cntA[ch[i]]++;

    for(i=;i<=N;i++)  cntA[i]+=cntA[i-];

    for(i=N;i>=;i--)  sa[cntA[ch[i]]--]=i;

    Rank[sa[]]=;

    for(i=;i<=N;i++)

    {

        Rank[sa[i]]=Rank[sa[i-]];

        if(ch[sa[i]]!=ch[sa[i-]]) Rank[sa[i]]++;

    }

    for(int L=;Rank[sa[N]]<N;L<<=)

    {

        for(i=;i<=N;i++) cntA[i]=cntB[i]=;

        for(i=;i<=N;i++) cntA[A[i]=Rank[i]]++;

        for(i=;i<=N;i++) cntB[B[i]=(i+L<=N)?Rank[i+L]:]++;

        for(i=;i<=N;i++) cntA[i]+=cntA[i-];

        for(i=;i<=N;i++) cntB[i]+=cntB[i-];

        for(i=N;i>=;i--) tsa[cntB[B[i]]--]=i;

        for(i=N;i>=;i--) sa[cntA[A[tsa[i]]]--]=tsa[i];

        Rank[sa[]]=;

        for(i=;i<=N;i++)

        {

            Rank[sa[i]]=Rank[sa[i-]];

            if(A[sa[i]]!=A[sa[i-]]||B[sa[i]]!=B[sa[i-]]) Rank[sa[i]]++;

        }

    }

    for (i=,j=;i<=N;i++)

    {

        if(j) j --;

        while (ch[i+j]==ch[sa[Rank[i]-]+j]) j++;

        ht[Rank[i]]=j;

    }

}

int main()

{

    scanf("%s",str1+);

    scanf("%s",str2+);

    int L1=strlen(str1+);

    int L2=strlen(str2+);

    for(int i=;i<=L1;i++) ch[i]=str1[i]-;

    ch[L1+]=;

    for(int i=;i<=L2;i++) ch[i+L1+]=str2[i]-;

    N=L1+L2+;

    solve();

    for(int i = ; i <= N; i++)

    {

        if((sa[i]<=L1)!=(sa[i-]<=L1))

            ans = max(ans, ht[i]);

    }

    printf("%d\n",ans);

    return ;

}