POJ 1743 (后缀数组+不重叠最长重复子串)

时间：2023-06-07 11:28:50

题目链接: http://poj.org/problem?id=1743

题目大意：楼教主の男人八题orz。一篇钢琴谱，每个旋律的值都在1~88以内。琴谱的某段会变调，也就是说某段的数可以加减一个旋律范围的值。问这个谱子内最长不重叠的重复部分大小。

解题思路：

网上题解已经泛滥的题。很多细节都被先辈大神总结了。

在当年后缀数组还不是热门的时候，这题确实是神题。

首先对于旋律变调的处理：

比如123，123，ans=3。

变调之后：456,123，ans=0？不ans=3。

所以不能使用旋律的初始值。应该取每个旋律前后的差值，这样就能保证某段无论怎么变调，都和原来一样。

不过这样就变成n-1个旋律，并且ans会-1，可以拿笔算几组看看。

对于取差值后的n-1个旋律，计算SA和LCP。   PS。很多人SA模板都是有问题的，并且推荐自动末尾补0的SA模板，不容易出现问题。

要求不重叠的重复部分大小，这里套用网上被传承N遍的奇葩结论：

将height数组分组，每组内的后缀之间的height都要大于len，如果每组内的后缀之间的最长公共前缀有大于len的而且这两个后缀的SA之差大于len就说明存在长度至少为len的不重复子串。求最长公共前缀就要用到height数组，因为这组中任意两个后缀的公共前缀必定是某些height值中的最小值，而这个值如果最大则一定是这组中height中的最大值。

由于SA数组按字典序来的，二分SA数组长度。如果len符合要求，则先记录。再向右找更大的，否则向左。注意二分的时候ans初始值为0，不然当n=1的时候，等于没有二分就return了一个ans。

#include "cstring"

#include "cstdio"

#include "string"

#include "iostream"

using namespace std;

#define maxn 23000

int n,r[maxn],tmp[maxn];

template <class T>

inline bool read(T &ret)

{

    char c;

    int sgn;

    if(c=getchar(),c==EOF) return ; //EOF

    while(c!='-'&&(c<''||c>'')) c=getchar();

    sgn=(c=='-')?-:;

    ret=(c=='-')?:(c-'');

    while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');

    ret*=sgn;

    return ;

}

struct Suffix

{

    int sa[maxn],rk[maxn],height[maxn];

    int t[maxn],t2[maxn],c[maxn],m;

    void init() {m=;}

    int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];}

    void build()

    {

        int i,k,p,*x=t,*y=t2;

        r[n++]=;

        for (i=; i<m; i++) c[i]=;

        for (i=; i<n; i++) c[x[i]=r[i]]++;

        for (i=; i<m; i++) c[i]+=c[i-];

        for (i=n-; i>=; i--) sa[--c[x[i]]]=i;

        for (k=,p=; k<n; k*=,m=p)

        {

            for (p=,i=n-k; i<n; i++) y[p++]=i;

            for (i=; i<n; i++) if (sa[i]>=k) y[p++]=sa[i]-k;

            for (i=; i<m; i++) c[i]=;

            for (i=; i<n; i++)  c[x[y[i]]]++;

            for (i=; i<m; i++) c[i]+=c[i-];

            for (i=n-; i>=; i--) sa[--c[x[y[i]]]]=y[i];

            swap(x,y);

            p=;

            x[sa[]]=;

            for (i=; i<n; i++) x[sa[i]]=cmp(y,sa[i-],sa[i],k)?p-:p++;

        }

        n--;

    }

    void LCP()

    {

        int i,j,k=;

        for (i=; i<=n; i++) rk[sa[i]]=i;

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

        {

            if (k) k--;

            j=sa[rk[i]-];

            while (r[i+k]==r[j+k]) k++;

            height[rk[i]]=k;

        }

    }

    bool judge(int len)

    {

        int l=sa[],r=sa[];

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

        {

            if(height[i]<len)

            {

                l=sa[i];r=sa[i];

                continue;

            }

            l=min(l,sa[i]);

            r=max(r,sa[i]);

            if(r-l>len) return true;

        }

        return false;

    }

    int BinarySearch()

    {

        int l=,r=n,mid,ans=;//注意ans=0，不然当n=1的时候返回的是没赋值的ans

        while(l<=r)

        {

            int mid=l+(r-l)/;

            if(judge(mid)) {ans=mid;l=mid+;}

            else r=mid-;

        }

        return ans;

    }

};

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out1.txt","w",stdout);

    while(read(n)&&n)

    {

        for(int i=; i<n; i++) read(tmp[i]);

        for(int i=; i<n-; i++) {r[i]=tmp[i+]-tmp[i]+;}

        Suffix a;

        a.init();

        a.build();

        a.LCP();

        int ans=a.BinarySearch();

        if(ans<) printf("0\n");

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

    }

}
13560509 neopenx 1743 Accepted 840K 407MS C++ 2761B 2014-10-24 10:20:38

相关文章