poj1743 Musical Theme 后缀数组

题目链接：点击打开链接

文章转载自：xuanqis.com

Description:

A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the range 1..88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the notion of musical timing; but, this programming task is about notes and not timings.
Many composers structure their music around a repeating &qout;theme&qout;, which, being a subsequence of an entire melody, is a sequence of integers in our representation. A subsequence of a melody is a theme if it:
is at least five notes long
appears (potentially transposed — see below) again somewhere else in the piece of music
is disjoint from (i.e., non-overlapping with) at least one of its other appearance(s)

Transposed means that a constant positive or negative value is added to every note value in the theme subsequence.
Given a melody, compute the length (number of notes) of the longest theme.
One second time limit for this problem’s solutions!

Input

The input contains several test cases. The first line of each test case contains the integer N. The following n integers represent the sequence of notes.
The last test case is followed by one zero.

Output

For each test case, the output file should contain a single line with a single integer that represents the length of the longest theme. If there are no themes, output 0.

Sample Input

30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80
0

Sample Output

5

Hint

Use scanf instead of cin to reduce the read time.

思路

求不可重叠最长重复子串,首先因为是旋律，所以转换成旋律，为避免最后一个字符干扰加上90，然后通过后缀数组方法构造height，求的是长度，就二分可能的长度，一个个的试能不能达到该长度。注意的是最后比较的是长度是否大于4，因为求出的是旋律的长度，而一个旋律两个字符，两个旋律，三个字符。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 20005;

int SA[MAXN], rank[MAXN], Height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m;

void Rsort()
{
    for(int i=0;i<=m;i++) tax[i]= 0;
    for(int i =1; i<=n;i++) tax[rank[tp[i]]]++;
    for(int i=1;i<=m;i++)  tax[i]+=tax[i-1];
    for(int i=n;i>=1;i--)  SA[tax[rank[tp[i]]]--]=tp[i];
}

int cmp(int *f, int x, int y, int w)
{
    return f[x]==f[y] && f[x+w]==f[y+w];
}

void Suffix()
{
    for(int i=1;i<=n;i++)rank[i]=a[i],tp[i]=i;
    m=180;Rsort();


    for(int w = 1,p = 1, i; p<n; w+=w,m=p)
    {
        for(p=0,i=n-w+1; i<=n; i++) tp[++p]=i;
        for(i=1;i<=n;i++) if (SA[i]>w)  tp[++p] = SA[i]-w;

        Rsort(),swap(rank,tp),rank[SA[1]]=p=1;

        for(i=2;i<=n;i++)
            rank[SA[i]]=cmp(tp,SA[i], SA[i-1], w)? p:++p;
    }

    int j,k=0;
    for(int i=1;i<=n;Height[rank[i++]]=k)
        for(k=k?k-1:k, j=SA[rank[i]-1];a[i+k]==a[j+k]; ++k);
}

int check(int n,int k)
{
    int maxn=SA[1],minn=SA[1];
    for(int i=2;i<=n;i++)
    {
        if(Height[i]<k)//两个长度不够，重新置 
            maxn=minn=SA[i];
        else
        {
            if(maxn<SA[i])  //maxn尽可能后面，minn尽可能前面，就更能不重叠 
                maxn=SA[i];
            if(minn>SA[i])  
                minn=SA[i];
            if(maxn-minn>k)  //没有重叠，可以达到这个长度 
                return 1;
        }
    }
    return 0;
}


int main()
{
    //freopen("2.txt", "r", stdin);
   while( scanf("%d",&n),n){ //输入元素个数 
    for(int i=1;i<=n;i++) //输入元素 
        scanf("%d", &a[i]);

    for (int i=1;i<n;i++) //按照题目要求转化 
        a[i]=(a[i+1]-a[i])+90; //加上 
    Suffix();  //后缀数组构造height 
    int ans=-1;  //答案初始化为负1 
    int l=1,r=n/2;  //二分答案，答案处于1~n/2之间 
    while(l<=r)
    {
        int mid=(l+r+1)>>1;//二分 
        if(check(n,mid)) //判断是否能达到这个长度 
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    if(ans<4)printf("0\n");  //五个字符，四个调的变化 
    else printf("%d\n", ans+1);
   }
}