Musical Theme
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 15903 | Accepted: 5497 |
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:
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.
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
其实就是求两个重复子串，不相交，用后缀数组，由题，因为，两个子串不一定要相同，可以是同时加上一个数，所以，我们可以用相邻的两位相减的方法，得到一组值，这样得到了height数组，就可以分成两组，在大于x的那一个组，只要存在差值比x大，那么就可以知道，一定存在这个解！
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn 200500
int wa[maxn],wb[maxn],ws[maxn],wv[maxn],wsd[maxn],r[maxn],ans[maxn];
char str[maxn];
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int c0(int *r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int *r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];}
void sort(int *r,int *a,int *b,int n,int m)
{
int i;
for(i=0;i<n;i++) wv[i]=r[a[i]];
for(i=0;i<m;i++) wsd[i]=0;
for(i=0;i<n;i++) wsd[wv[i]]++;
for(i=1;i<m;i++) wsd[i]+=wsd[i-1];
for(i=n-1;i>=0;i--) b[--wsd[wv[i]]]=a[i];
return;
}
void dc3(int *r,int *sa,int n,int m)
{
int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
r[n]=r[n+1]=0;
for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
sort(r+2,wa,wb,tbc,m);
sort(r+1,wb,wa,tbc,m);
sort(r,wa,wb,tbc,m);
for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
if(p<tbc) dc3(rn,san,tbc,p);
else for(i=0;i<tbc;i++) san[rn[i]]=i;
for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
if(n%3==1) wb[ta++]=n-1;
sort(r,wb,wa,ta,m);
for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
for(i=0,j=0,p=0;i<ta && j<tbc;p++)
sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
for(;i<ta;p++) sa[p]=wa[i++];
for(;j<tbc;p++) sa[p]=wb[j++];
return;
}
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) wsd[i]=0;
for(i=0;i<n;i++) wsd[x[i]=r[i]]++;
for(i=1;i<m;i++) wsd[i]+=wsd[i-1];
for(i=n-1;i>=0;i--) sa[--wsd[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
//桶排
for(i=0;i<m;i++) wsd[i]=0;
for(i=0;i<n;i++) wsd[wv[i]]++;
for(i=1;i<m;i++) wsd[i]+=wsd[i-1];
for(i=n-1;i>=0;i--) sa[--wsd[wv[i]]]=y[i];
//桶排
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
return;
}
int main()
{
int n,n1;
while(scanf("%s",str)!=EOF){
n=strlen(str);n1=n;
str[n]='{';
scanf("%s",str+n+1);
n=strlen(str);
for(int i=0;i<n;i++)
r[i]=str[i];
int m=300;
r[n]=0;
//da(r,ans,n+1,m);
dc3(r,ans, n+1,m);
calheight(r,ans,n);
int maxx=0;
for(int i=2;i<=n;i++){//height从１开始
if((ans[i]>n1&&ans[i-1]<n1)||(ans[i]<n1&&ans[i-1]>n1)){
maxx=max(maxx,height[i]);
}
}
printf("%d\n",maxx);
}
return 0;
}