[POJ1743]Musical Themes 樂曲主題 後綴數組、 （也可以用hash+二分做的~）

[POJ1743]Musical Themes 樂曲主題 後綴數組、 （也可以用hash+二分做的~）

題意：

Description

我們用N(1 <= N <=5000)個音符的序列來表示一首樂曲，每個音符都是1..88范圍內的整數，每個數表示鋼琴上的一個鍵。很不幸這種表示旋律的方法忽略了音符的時值，但這項編程任務是關於音高的，與時值無關。

許多作曲家圍繞一個重復出現的“主題”來構建樂曲。在我們的樂曲表示法中，“主題”是整個音符序列的一個子序列，它需要滿足如下條件：

• 長度至少為5個音符
• 在樂曲中重復出現(可能經過轉調，見下)
• 重復出現的同一主題不能重疊

  “轉調”的意思是主題序列中每個音符都被加上或減去了同一個整數值。

  給定一段樂曲，計算其中最長主題的長度(即音符數)。

  Input

  輸出文件的第一行包含整數N。下面的每一行(最後一行可能除外)包含20個整數，表示音符序列。最後一行可能少於20個音符。

  Output

  輸出文件應只含一個整數，即最長主題的長度。如果樂曲中沒有主題，那麼輸出0。

  Sample Input

  3025 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 1882 78 74 70 66 67 64 60 65 80

  Sample Output

  5

  HINT

   

  樣例中這個長度為5的主題是輸入文件中第一行的最後5個音符和第二行開頭5個音符

   

  Source

  USACO

  Best Solution

  C C++ Pascal NULL 80643.wyfcyx
  (0ms,1100KB,2168B) 21804.Ares
  (72ms,292KB,561B) [Submit][Status][Web Board] 

  ---

  Powered by LLQ. ?2012-2014 長春吉大附中實驗學校.

   

  題解：

  啊，寫個後綴數組，然後二分check時根據height分組，使每一段都滿足height足夠長，掃一遍，如果裡面離的最遠兩個沒重合（sa的差足夠大），就return 1。。。

   

  代碼：

   

  #include 
  #include 
  #include 
  #include 
  #define N 21000
  using namespace std;
  int s[N];
  int sa[N],rank[N],h[N],n,m,len;
  int cnt[N],val[N],stk[N],_val[N],top;
  bool issame(int a,int b,int hl)
  {
  	return val[a]==val[b]&&
  	((a+hl>=len&&b+hl>=len)||(a+hl=0;i--)sa[--cnt[val[i]]]=i;
  
  	for(k=1;;k++)
  	{
  		top=0,hl=1<<(k-1);
  		for(i=0;i=len)stk[top++]=sa[i];
  		for(i=0;i=hl)stk[top++]=sa[i]-hl;
  
  		for(i=0;i=0;i--)sa[--cnt[val[stk[i]]]]=stk[i];
  
  		for(lim=i=0;imid)return 1;
  	}
  	return 0;
  }
  int main()
  {
  //	freopen("test.in","r",stdin);
  	int i,j,k;
  	scanf("%d",&len);
  	scanf("%d",&s[0]);
  	for(i=1;i>1;
  		if(check(mid))l=mid;
  		else r=mid-1;
  	}
  	if(ans>=4)printf("%d\n",ans+1);else puts("0");
  	return 0;
  }