Pku1743 Musical Theme詳細(xì)解題報告后綴數(shù)組求不重疊的最長重復(fù)子串

1、Pku1743 Musical Theme/*Name: pku1743Copyright: ecjtu_acmAuthor: yimaoDate: 16/02/11 13:35Description:二分答案，后綴數(shù)組求不重疊的最長重復(fù)子串*/一、題目DescriptionA 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 b

2、ut 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 rep

3、resentation. A subsequence of a melody is a theme if it:is at least five notes longappears (potentially transposed - see below) again somewhere else in the piece of musicis disjoint from (i.e., non-overlapping with) at least one of its other appearance(s)Transposed means that a constant positive or

4、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 problems solutions!InputThe input contains several test cases. The first line of each test case contains the integer N. The fo

5、llowing n integers represent the sequence of notes.The last test case is followed by one zero.OutputFor 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 Input3025 2730 34 3945 5

6、26069 7969 60 52 45 39 34 30 26 22 1882 7874 70 6667 646065 800Sample Output5HintUse scanf instead of cin to reduce the read time.SourceLouTianchengPOJ二、題目大意及分析【前話】我的poj第200題；樓教主男人八題之一；3xian在status里以絕對的時空優(yōu)勢排第一；紀(jì)念我的百度空間訪問量破2000 ；我的第一道后綴數(shù)組題；典型的二分答案，用后綴數(shù)組求不重疊的最長重復(fù)子串；網(wǎng)上看題解不下10篇，綜合之后才知道他們大概在說些什么，感嘆前人栽樹，后

7、人乘涼；可以證明本篇文章應(yīng)該是字?jǐn)?shù)最多的pku1743題解了；【題意】給定一個正整數(shù)N(N=20000)，然后是N個整數(shù)xi，(1=xi=88, 1=i=k（枚舉的答案），我們只需判斷sa1，sa2 的差值是否大于k即可，這樣sa1 和sa2的LCP長度就滿足了條件，且不會相交了，寫個 串就好理解了，問題是為什么一直掃描，不斷更新最大最小的sai呢？我說兩個情況：情況 1： height2=k；初始 mmin=sa1,mmax=sa1;從 i=2 開始循環(huán)，有更新 mmin=sa2,mmax=sa2，然后是 height3=k，更新 mmin，mmax，此時 mmin， mmax 是 sa2,

8、sa3的最小最大值，也就是 兩個子串打頭的字符在整個序列里的下標(biāo)，如果mmax-mmin=k，也即下標(biāo)之差=k，那么 就保證了這個長度為k的公共部分在串sa2和串sa3不是重疊的，就返回1，否則繼續(xù)循 環(huán)。情況2： height2=k，height3=k；（循環(huán)到2后不滿足條件）初始 mmin=sa1,mmax=sa1;從 i=2 開始循環(huán)，更新后 mmin，mmax 是 sa1,sa2的最小 最大值 mmin=sa2,mmax=sa2，然后是 i=3,更新后 mmin,mmax 是 sa1,sa2,sa3的最小最 大值，那么如果mmax-mmin=k，就滿足條件返回1。（為什么呢？因為由he

9、ight2=k， height3=k就可以推出sa1,sa3的LCP=k，如果你不理解，那只能說明你不知道height,sa 是什么。）到這里就可以看出Check（）的精華就是線性掃描通過sa把height值=k的合并到 了一起來，也就是論文上說的分組了，同時mmin，mmax的不斷更新可以最大范圍的查找 到LCP=k且互不相交的情況。其他情況不寫了。好累好累。呃，還有主函數(shù)里ans要+1輸出，要判斷是否大于5；/*1743 Accepted 804K 219MS C+ 2038B 2011-02-16 11:35:10 */#include#include#define N 20010usi

10、ng namespace std;int rN;int wssN,waN,wbN,wvN;int saN,rankN,heightN;int cmp(int *r,int a,int b,int l)return ra=rb&ra+l=rb+l;void Da(int *r,int *sa,int n,int m) int i,j,p,*x=wa,*y=wb,*t; for(i=0;im;i+)wssi=0; for(i=0;in;i+)wssxi=ri+; for(i=1;i=0;i-)sa-wssxi=i; for(j=1,p=1;pn;j*=2,m=p) for(p=0,i=n-j;in

11、;i+)yp+=i;for(i=0;i=j)yp+=sai-j;for(i=0;in;i+)wvi=xyi; for(i=0;im;i+)wssi=0;for(i=0;in;i+)wsswvi+;for(i=1;i=0;i-)sa-wsswvi=yi;for(t=x,x=y,y=t,p=1,xsa0=0,i=1;in;i+) xsai=cmp(y,sai-1,sai,j)?p-1:p+;return;void Cal_height(int *r,int *sa,int n) int i,j,k=0;for(i=1;i=n;i+)ranksai=i;for(i=0;in;heightranki+=k)for(k?k-:0,j=saranki-1;ri+k=rj+k;k+);int Check(int k,int n)int i,mmin=sa1,mmax=sa1;for(i=2;i=n;i+)if(heighti=k) return 1;return 0;int Binary_result(int st,int e