POJ 1743 Musical Theme（后缀数组）

题意：
给定一个字符串，求最长重复子串，可以是完全相等，也可以是每一位相减都相等，并且这两个子串不能重叠。

思路：

先二分答案，把题目变成判定性问题：判断是否存在两个长度为 k 的子串是相同的，且不重叠。解决这个问题的关键还是利用height 数组。把排序后的后缀分成若干组，其中每组的后缀之间的 height 值都不小于 k。

分完组后，寻找每组当中sa值的最大值和最小值，只要相减>k那么就是满足的，这点很容易想吧。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 #include<set>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef pair<int,int> pll;
 14 const int INF = 0x3f3f3f3f;
 15 const int maxn=40000+5;
 16 
 17 int s[maxn];
 18 int sa[maxn],t[maxn],t2[maxn],c[maxn],n;
 19 int Rank[maxn],height[maxn];
 20 
 21 void build_sa(int m)
 22 {
 23     int *x=t,*y=t2;
 24     //基数排序
 25     for(int i=0;i<m;i++)    c[i]=0;
 26     for(int i=0;i<n;i++)    c[x[i]=s[i]]++;
 27     for(int i=1;i<m;i++)    c[i]+=c[i-1];
 28     for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
 29     for(int k=1;k<=n;k<<=1)
 30     {
 31         int p=0;
 32         //直接利用sa数组排序第二关键字
 33         for(int i=n-k;i<n;i++)  y[p++]=i;
 34         for(int i=0;i<n;i++)    if(sa[i]>=k)    y[p++]=sa[i]-k;
 35         //基数排序第一关键字
 36         for(int i=0;i<m;i++)    c[i]=0;
 37         for(int i=0;i<n;i++)    c[x[y[i]]]++;
 38         for(int i=1;i<m;i++)    c[i]+=c[i-1];
 39         for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
 40         //根据sa和y计算新的x数组
 41         swap(x,y);
 42         p=1;
 43         x[sa[0]]=0;
 44         for(int i=1;i<n;i++)
 45             x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
 46         if(p>=n)
 47             break;
 48         m=p;                //下次基数排序的最大值
 49     }
 50 }
 51 
 52 void getHeight()
 53 {
 54     int i,j,k=0;
 55     for(i=1;i<n;i++)  Rank[sa[i]]=i;
 56     for(i=0;i<n-1;i++)  
 57     {
 58         if(k)  k--;
 59         int j=sa[Rank[i]-1];
 60         while(s[i+k]==s[j+k])  k++;
 61         height[Rank[i]]=k;
 62     }
 63 }
 64 
 65 bool check(int k)
 66 {
 67     int mi=INF,mx=-INF;
 68     for(int i=2;i<=n-1;i++)
 69     {
 70         if(height[i]>=k)
 71         {
 72             mi=min(mi,min(sa[i],sa[i-1]));
 73             mx=max(mx,max(sa[i],sa[i-1]));
 74             if(mx-mi>k) return true;
 75         }
 76         else
 77         {
 78             mi=INF;
 79             mx=-INF;
 80         }
 81     }
 82     return false;
 83 }
 84 
 85 int main()
 86 {
 87     //freopen("in.txt","r",stdin);
 88     while(~scanf("%d",&n) && n)
 89     {
 90         for(int i=0;i<n;i++) scanf("%d",&s[i]);
 91         for(int i=0;i<n-1;i++)  s[i]=s[i+1]-s[i]+88;
 92         s[n-1]=0;
 93         build_sa(200);
 94         getHeight();
 95         int ans=0;
 96         int l=4,r=n;
 97         while(l<=r)
 98         {
 99             int mid=(l+r)>>1;
100             if(check(mid)) {ans=mid;l=mid+1;}
101             else r=mid-1;
102         }
103         ans++;
104         printf("%d
",ans<5?0:ans);
105     }
106     return 0;
107 }