USACO Section 5.1 Musical Themes - 題目轉換以及KMP..

    先寫了一個N^3的裸搜試了試~~結果還過了12個點~~囧...然後就想起優化...主要思想是要利用前面已經搜尋過的..盡量減少重複的判斷搜尋...根據這些特征自然而然的想到了KMP...但由于題目中是要求兩列每位對應差相等而不是說兩列完全相等...是以寫了一晚上搞得十分蛋疼..還是搞不出來...

     再看了下樣例..發現題目可以轉化!!! 其實差了一個自然數的兩列..若寫成相鄰前後之差的形式就會變成完全相同的兩列..如1 2 4 5 4 5 7 1 寫成相鄰前後之差的形式為 1 2 1 -1 1 2 1 -6 那麼看出最長公共部分是有兩個1 2 ...那麼這串中符合題目要求最長的主旋律是3個音節( 因為這個1,2是1 2 4 又是 4 5 7 不難了解為啥實際結果比轉化後的最長結果會大一.)...

     經過這麼轉化..題目就變成了給出一個串...找出其中最長的兩段不相鄰的相同子串...我最先想到的KMP就可以完美實作了!!..N^2的算法..先枚舉第一個段的起點..從1~N..将這個起點到N的段構造好Fail指針( 同最本質的KMP..指向離自己最近的相同字首尾部部分 ) .. 構造好後..從第一段起點的後面一個點掃到N...就是用後面一段在先做好的長串裡找最長公共子串...但要注意題目的要求..兩段不能有公共部分...并且在通過轉化後..這個條件又等同了兩段間至少要有一個數..不能相鄰...注意了這個條件的處理...這個KMP還是很好寫的..

/*  
ID: zzyzzy12   
LANG: C++   
TASK: theme
*/      
#include<iostream>      
#include<istream>  
#include<stdio.h>     
#include<string.h>      
#include<math.h>      
#include<stack>
#include<map>
#include<algorithm>      
#include<queue>   
#define oo 2000000005  
#define ll long long  
#define pi (atan(2)+atan(0.5))*2 
using namespace std; 
int a[5005],n,Fail[5005];
int main()  
{  
      freopen("theme.in","r",stdin);   
      freopen("theme.out","w",stdout); 
      int i,j,m,k,ans;
      bool f;
      scanf("%d",&n);
      for (i=1;i<=n;i++) scanf("%d",&a[i]); 
      for (i=1;i<n;i++) a[i]=a[i+1]-a[i];
      n--;  ans=0;
      for (i=1;i<=n;i++)
      { 
            Fail[i]=i-1; 
            for (j=i+1;j<=n;j++)    
            {
                  k=Fail[j-1];
                  while (k>=i && a[k+1]!=a[j]) k=Fail[k];
                  if (a[k+1]==a[j]) Fail[j]=k+1;
                     else  Fail[j]=k;
            }    
            m=0;  j=i+1;
            while (j<=n)
            {
                  f=true;
                  while (i+m<j-m-1 && a[i+m]==a[j])
                  {
                        j++;
                        m++;
                        f=false;      
                  }
                  if (f)
                  {
                        j++;
                        continue;      
                  } 
                  if (m+1>ans) ans=m+1;
                  k=Fail[i+m-1]; 
                  while (k>=i && a[k+1]!=a[j]) k=Fail[k];
                  if (a[k+1]==a[j]) m=k-i+1;
                     else m=0;
            }
      } 
      if (ans<5) ans=0;
      printf("%d\n",ans);
      return 0;     
}