HihoCoder1415后缀数组三·重复旋律3

重复旋律3

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。

旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？

输入

共两行。一行一个仅包含小写字母的字符串。字符串长度不超过 100000。

输出

一行一个整数，表示答案。

样例输入

abcdefg

abacabca

样例输出

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 ;

}

没有找到原因，开始用字符串一直错，改成数组就AC了。也不知道为什么。过几天再看看吧。