POJ - 1743 Musical Theme （后缀数组）
题目链接：POJ - 1743 （不可重叠最长子串）
题意：有N(1<=N<=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的子串，它需要满足如下条件：
1.长度至少为5个音符。
2.在乐曲中重复出现（就是出现过至少两次）。(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)
3.重复出现的同一主题不能有公共部分。
题解：先求出相邻音符的差，因为转调的话肯定差也是不会变的。然后问题就变成了求不可重叠最长重复子串长度，用后缀数组就可以，重点在不可重叠，因为不能重叠，两个子串要隔至少一个位置，不然就相当于后边子串的首音符和前边子串的尾音符重合了，（因为差值是当前和前一个音符的差值），所以只要将限定条件从max-min>=k改为max-min>k就可以了。二分答案，将问题变为判断是否存在两个长度为k的子串是相同的，且不重叠。如果存在一个区间内的height值都大于等于k，并且存在两个后缀的距离大于k，则说明存在这样的字符串。
倍增法版本：（憨憨的我以为DC3 t了结果是卡输入输出）
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #include<iostream> 5 #include<cmath> 6 #include<cstring> 7 using namespace std; 8 9 const int INF=0x3f3f3f3f; 10 const int maxn = 1e6+10; 11 int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn]; 12 int rnk[maxn],height[maxn],s[maxn]; 13 int r[maxn],n; 14 15 //sa:字典序中排第i位的起始位置在str中第sa[i] sa[1~n]为有效值 16 17 //rnk:就是str第i个位置的后缀是在字典序排第几 rnk[0~n-1]为有效值 18 19 //height：字典序排i和i-1的后缀的最长公共前缀 height[2~n]为有效值，第二个到最后一个 20 21 int cmp(int *r,int a,int b,int k) 22 { 23 return r[a]==r[b]&&r[a+k]==r[b+k]; 24 } 25 26 void getsa(int *r,int *sa,int n,int m)//n为添加0后的总长 27 { 28 int i,j,p,*x=wa,*y=wb,*t; 29 for(i=0; i<m; i++) wsf[i]=0; 30 for(i=0; i<=n; i++) wsf[x[i]=r[i]]++; 31 for(i=1; i<m; i++) wsf[i]+=wsf[i-1]; 32 for(i=n; i>=0; i--) sa[--wsf[x[i]]]=i; 33 p=1; 34 j=1; 35 for(; p<=n; j*=2,m=p){ 36 for(p=0,i=n+1-j; i<=n; i++) y[p++]=i; 37 for(i=0; i<=n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; 38 for(i=0; i<=n; i++) wv[i]=x[y[i]]; 39 for(i=0; i<m; i++) wsf[i]=0; 40 for(i=0; i<=n; i++) wsf[wv[i]]++; 41 for(i=1; i<m; i++) wsf[i]+=wsf[i-1]; 42 for(i=n; i>=0; i--) sa[--wsf[wv[i]]]=y[i]; 43 swap(x,y); 44 x[sa[0]]=0; 45 for(p=1,i=1; i<=n; i++) 46 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++; 47 } 48 } 49 50 void getheight(int *r,int n)//n为添加0后的总长 51 { 52 int i,j,k=0; 53 for(i=1; i<=n; i++) rnk[sa[i]]=i; 54 for(i=0; i<n; i++){ 55 if(k) 56 k--; 57 else 58 k=0; 59 j=sa[rnk[i]-1]; 60 while(r[i+k]==r[j+k]) 61 k++; 62 height[rnk[i]]=k; 63 } 64 } 65 66 bool check(int k) 67 { 68 bool flag=0; 69 int mx=-INF,mn=INF; 70 for(int i=2;i<=n;i++){ 71 if(height[i]>=k){ 72 mn=min(mn,min(sa[i],sa[i-1])); 73 mx=max(mx,max(sa[i],sa[i-1])); 74 if(mx-mn>k) return true; 75 } 76 else mx=-INF,mn=INF; 77 } 78 return false; 79 } 80 81 int main() 82 { 83 ios::sync_with_stdio(false); 84 cin.tie(0); 85 cout.tie(0); 86 while(cin>>n&&n){ 87 for(int i=0;i<n;i++) cin>>s[i]; 88 --n; 89 for(int i=0;i<n;i++) r[i]=s[i+1]-s[i]+100; 90 r[n]=0; 91 getsa(r,sa,n,200); 92 getheight(r,n); 93 int l=0,r=n/2; 94 int ans=0; 95 while(l<=r){ 96 int mid=l+r>>1; 97 if(check(mid)){ 98 ans=mid; 99 l=mid+1; 100 } 101 else r=mid-1; 102 } 103 if(ans>=4) cout<<ans+1<<endl; //因为当前ans是记录的差的长度，串的长度要+1 104 else cout<<0<<endl; 105 } 106 return 0; 107 }
DC3版本：
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #include<iostream> 5 #include<cmath> 6 #include<cstring> 7 using namespace std; 8 9 #define F(x) ((x)/3+((x)%3==1?0:tb)) 10 #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) 11 12 //sa:字典序中排第i位的起始位置在s中第sa[i] 13 14 //rnk:就是s第i个位置的后缀是在字典序排第几 15 16 //height：字典序排i和i-1的后缀的最长公共前缀 17 18 const int INF=0x3f3f3f3f; 19 const int MAXN = 3e6+10; 20 int sa[MAXN]; 21 int rankk[MAXN]; 22 int height[MAXN]; 23 int n; 24 int s[MAXN]; 25 int r[MAXN]; 26 int wa[MAXN],wb[MAXN],wv[MAXN]; 27 int wws[MAXN]; 28 29 void sort(int *r,int *a,int *b,int n,int m) 30 { 31 int i; 32 for(i=0;i<n;i++) wv[i]=r[a[i]]; 33 for(i=0;i<m;i++) wws[i]=0; 34 for(i=0;i<n;i++) wws[wv[i]]++; 35 for(i=1;i<m;i++) wws[i]+=wws[i-1]; 36 for(i=n-1;i>=0;i--) b[--wws[wv[i]]]=a[i]; 37 return; 38 } 39 40 int c0(int *r,int a,int b) 41 { 42 return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2]; 43 } 44 45 int c12(int k,int *r,int a,int b) 46 { 47 if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1); 48 else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1]; 49 } 50 51 void dc3(int *r,int *sa,int n,int m) 52 { 53 int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p; 54 r[n]=r[n+1]=0; 55 for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i; 56 sort(r+2,wa,wb,tbc,m); 57 sort(r+1,wb,wa,tbc,m); 58 sort(r,wa,wb,tbc,m); 59 for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++) 60 rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++; 61 if(p<tbc) dc3(rn,san,tbc,p); 62 else for(i=0;i<tbc;i++) san[rn[i]]=i; 63 for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3; 64 if(n%3==1) wb[ta++]=n-1; 65 sort(r,wb,wa,ta,m); 66 for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i; 67 for(i=0,j=0,p=0;i<ta && j<tbc;p++) 68 sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++]; 69 for(;i<ta;p++) sa[p]=wa[i++]; 70 for(;j<tbc;p++) sa[p]=wb[j++]; 71 return; 72 } 73 74 void calheight(int *r, int *sa, int n) 75 { 76 int i, j, k = 0; 77 for (i = 1; i <= n; ++i) rankk[sa[i]] = i; 78 for (i = 0; i < n; height[rankk[i++]] = k) 79 for (k ? k-- : 0, j = sa[rankk[i] - 1]; r[i + k] == r[j + k]; ++k); 80 return; 81 } 82 83 bool check(int k) 84 { 85 bool flag=0; 86 int mx=-INF,mn=INF; 87 for(int i=2;i<=n;i++){ 88 if(height[i]>=k){ 89 mn=min(mn,min(sa[i],sa[i-1])); 90 mx=max(mx,max(sa[i],sa[i-1])); 91 if(mx-mn>k) return true; 92 } 93 else mx=-INF,mn=INF; 94 } 95 return false; 96 } 97 98 int main() 99 { 100 ios::sync_with_stdio(false); 101 cin.tie(0); 102 cout.tie(0); 103 while(cin>>n&&n){ 104 for(int i=0;i<n;i++) cin>>s[i]; 105 --n; 106 for(int i=0;i<n;i++) r[i]=s[i+1]-s[i]+100; 107 r[n]=0; 108 dc3(r,sa,n+1,200); 109 calheight(r,sa,n); 110 int l=0,r=n/2; 111 int ans=0; 112 while(l<=r){ 113 int mid=l+r>>1; 114 if(check(mid)){ 115 ans=mid; 116 l=mid+1; 117 } 118 else r=mid-1; 119 } 120 if(ans>=4) cout<<ans+1<<endl; ////因为当前ans是记录的差的长度，串的长度要+1 121 else cout<<0<<endl; 122 } 123 return 0; 124 }
美的集团公司福利 135人发布
