http://poj.org/problem?id=1743

題意：給n個數組成的串，求是否有多個“相似”且不重疊的子串的長度大于等于5，兩個子串相似當且僅當長度相等且每一位的數字差都相等。

題解：后綴數組+二分+不可重疊最長重復子串

C++版本一

/* *@Author: STZG *@Language: C++ */ //#include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=200000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[N],s[N]; int wa[N],wb[N],c[N]; char str; struct node{}; int cmp(int *r,int a,int b,int l){return r[a]==r[b] && r[a+l]==r[b+l]; } int sa[N],Rank[N],height[N]; void SA(int *r,int n,int m){for(int i=0;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[wa[i]=r[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[wa[i]]--]=i;for(int k=1;k<=n;k<<=1){int num=0;for(int i=n-k+1;i<=n;i++)wb[++num]=i;for(int i=1;i<=n;i++)if(sa[i]>k)wb[++num]=sa[i]-k;for(int i=0;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[wa[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[wa[wb[i]]]--]=wb[i],wb[i]=0;swap(wa,wb);wa[sa[1]]=1;num=1;for(int i=2;i<=n;i++)wa[sa[i]]=cmp(wb,sa[i],sa[i-1],k)?num:++num;if(num==n)break;m=num;} } void calheight(const int *r,int n) {int i,j,k=0;for(i=1;i<=n+1;i++) Rank[sa[i]]=i;for(i=1;i<=n;height[Rank[i++]]=k)for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);return; } bool sloved(int mid,int n){int maxn=sa[1],minn=sa[1];for (int i=2;i<=n;++i){//不管height有多大，我只取mid這么長，因為做差了，所以實際上height[i]對應的是height[i]+1這么長的原序列if (height[i]>=mid-1){//LCP(i,k)=min(LCP(i,j),LCP(j,k)) (i<=j<=k)//使height始終滿足條件，保證上面式子取min始終大于等于mid，因為要保證至少有一處重復maxn=max(maxn,sa[i]);minn=min(minn,sa[i]);}//相鄰2個肯定是最相似的，如果相鄰2個都小于mid，那么與其他之前的串也不會是大于等于mid了else maxn=minn=sa[i];//推過來的過程中有不滿足的就斷了，也是一個起始點if (maxn-minn>=mid){//因為是后綴，小的串是大的串的一部分，所以只要兩個串的差大于等于mid就能容下小的串，就不會重疊//這里本質上應該是maxn+1-(minn+1)>=midreturn 1;}}return 0; }int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(~scanf("%d",&n)&&n){for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<n;i++){s[i]=a[i+1]-a[i]+89;}s[n]=0;SA(s,n-1,178);calheight(s,n-1);int l=0;int r=n/2;int mid;ans=0;while(l<=r){mid=(l+r)>>1;if(sloved(mid,n-1)){ans=mid;l=mid+1;}else{r=mid-1;}}cout<<((ans<=4)?0:ans)<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

#include<stdio.h> #include<algorithm> #define ll long long #define pb push_back #define INF 0x3f3f3f3f; #define fi first #define se second #define MP make_pair #define PI pair<int,int> #define lson l,m,rt<<1,ls,rs #define rson m+1,r,rt<<1|1,ls,rs #define test printf("here!!!\n") using namespace std; const int mx=2e4+10; int n,m; int a[mx]; int s[mx]; int sa[mx],tp[mx],rk[mx],rdx[mx],height[mx]; void get_SA() {for (int i=0;i<=m;++i) rdx[i]=0;for (int i=1;i<=n;++i) ++rdx[rk[i]];for (int i=1;i<=m;++i) rdx[i]+=rdx[i-1];for (int i=n;i>=1;--i) sa[rdx[rk[tp[i]]]--]=tp[i]; } void SA() {m=200;for (int i=1;i<=n;++i) rk[i]=(int)s[i],tp[i]=i;get_SA();for (int w=1,p=0;p<n;m=p,w<<=1){p=0;for (int i=n-w+1;i<=n;++i) tp[++p]=i;for (int i=1;i<=n;++i){if (sa[i]>w) tp[++p]=sa[i]-w;}get_SA();swap(tp,rk);rk[sa[1]]=p=1;for (int i=2;i<=n;++i)rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&((sa[i-1]+w>n&&sa[i]+w>n)||(sa[i-1]+w<=n&&sa[i]+w<=n&&tp[sa[i-1]+w]==tp[sa[i]+w])))?p:++p;//此時的tp為之前的rk，即之前的rk排行,構造新rk} } void getheight() {int k=0;for (int i=1;i<=n;++i){if (rk[i]==1) continue;if (k) --k;int j=sa[rk[i]-1];while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;height[rk[i]]=k;} } int main() {while (~scanf("%d",&n)&&n){for (int i=1;i<=n;++i){scanf("%d",&a[i]);}for (int i=1;i<n;++i){s[i]=a[i+1]-a[i]+90;}--n;//care!SA();getheight();int l=0;int r=(n+1)/2;//care!while (l<=r){int flag=0;int mid=l+r>>1;//二分答案int maxn=sa[1],minn=sa[1];for (int i=2;i<=n;++i){//不管height有多大，我只取mid這么長，因為做差了，所以實際上height[i]對應的是height[i]+1這么長的原序列if (height[i]>=mid-1)//LCP(i,k)=min(LCP(i,j),LCP(j,k)) (i<=j<=k){//使height始終滿足條件，保證上面式子取min始終大于等于mid，因為要保證至少有一處重復maxn=max(maxn,sa[i]);minn=min(minn,sa[i]);}//相鄰2個肯定是最相似的，如果相鄰2個都小于mid，那么與其他之前的串也不會是大于等于mid了else maxn=minn=sa[i];//推過來的過程中有不滿足的就斷了，也是一個起始點if (maxn-minn>=mid)//因為是后綴，小的串是大的串的一部分，所以只要兩個串的差大于等于mid就能容下小的串，就不會重疊{//這里本質上應該是maxn+1-(minn+1)>=midflag=1;break;}}if (flag){l=mid+1;}else r=mid-1;}r>=5?printf("%d\n",r):printf("0\n");} }

C++版本三

原博客

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 22222 #define INF (1<<30) int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; int cmp(int *r,int a,int b,int l){return r[a]==r[b] && r[a+l]==r[b+l]; } int sa[MAXN],rank[MAXN],height[MAXN]; void SA(int *r,int n,int m){int *x=wa,*y=wb;for(int i=0; i<m; ++i) ws[i]=0;for(int i=0; i<n; ++i) ++ws[x[i]=r[i]];for(int i=1; i<m; ++i) ws[i]+=ws[i-1];for(int i=n-1; i>=0; --i) sa[--ws[x[i]]]=i;int p=1;for(int j=1; p<n; j<<=1,m=p){p=0;for(int i=n-j; i<n; ++i) y[p++]=i;for(int i=0; i<n; ++i) if(sa[i]>=j) y[p++]=sa[i]-j;for(int i=0; i<n; ++i) wv[i]=x[y[i]];for(int i=0; i<m; ++i) ws[i]=0;for(int i=0; i<n; ++i) ++ws[wv[i]];for(int i=1; i<m; ++i) ws[i]+=ws[i-1];for(int i=n-1; i>=0; --i) sa[--ws[wv[i]]]=y[i];swap(x,y); x[sa[0]]=0; p=1;for(int i=1; i<n; ++i) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}for(int i=1; i<n; ++i) rank[sa[i]]=i;int k=0;for(int i=0; i<n-1; height[rank[i++]]=k){if(k) --k;for(int j=sa[rank[i]-1]; r[i+k]==r[j+k]; ++k);} }int n,a[MAXN],r[MAXN]; bool isok(int k){bool flag=0;int mx=-INF,mm=INF;for(int i=2; i<=n; ++i){if(height[i]>=k){mm=min(mm,min(sa[i],sa[i-1]));mx=max(mx,max(sa[i],sa[i-1]));if(mx-mm>k) return 1;}else{mx=-INF,mm=INF;}}return 0; } int main(){while(~scanf("%d",&n) && n){for(int i=0; i<n; ++i) scanf("%d",a+i);--n;for(int i=0; i<n; ++i) r[i]=a[i+1]-a[i]+88;r[n]=0;SA(r,n+1,176);int l=0,r=n>>1;while(l<r){int mid=l+r+1>>1;if(isok(mid)) l=mid;else r=mid-1;}if(l>=4) printf("%d\n",l+1);else printf("%d\n",0);}return 0; }

C++版本四

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string.h> #include <queue> //POJ1743 求不可重疊的最長重復子串（后綴數組） #define maxn 20005 using namespace std; int wa[maxn],wb[maxn],wv[maxn],Ws[maxn], Rank[maxn], height[maxn], sa[maxn]; int a[maxn]; //以下為倍增算法，套模板 /* height數組是從1到n的 height數組是排名相鄰的兩個后綴的最長公共前綴（公共長度） 字符串中的兩個子串的公共前綴想要最長，一定是在sa數組相鄰的 */ int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];} void da(const int *r,int *sa,int n,int m) //r為字符串(將其都轉化為int）,n為字符串長度，m為字符的取值范圍 {int i,j,p,*x=wa,*y=wb,*t; for(i=0;i<m;i++) Ws[i]=0; for(i=0;i<n;i++) Ws[x[i]=r[i]]++; for(i=1;i<m;i++) Ws[i]+=Ws[i-1]; for(i=n-1;i>=0;i--) sa[--Ws[x[i]]]=i; for(j=1,p=1;p<n;j*=2,m=p){ for(p=0,i=n-j;i<n;i++) y[p++]=i; for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0;i<n;i++) wv[i]=x[y[i]]; for(i=0;i<m;i++) Ws[i]=0; for(i=0;i<n;i++) Ws[wv[i]]++; for(i=1;i<m;i++) Ws[i]+=Ws[i-1]; for(i=n-1;i>=0;i--) sa[--Ws[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } return; } //求height數組 void calheight(const int *r,int *sa,int n) {int i,j,k=0;for(i=1;i<=n;i++) Rank[sa[i]]=i;for(i=0;i<n;height[Rank[i++]]=k)for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);return; } bool check(int k, int n) //k指代的是長度，二分法來推滿足的長度 {int t, max1=sa[0], min1=sa[0];for(t=1; t<=n; ++t){if(height[t]>=k){if(sa[t]<min1)min1=sa[t];if(sa[t]>max1)max1=sa[t];if(max1-min1>k)return true;}else {max1=min1=sa[t];}}return false; }int main() {int n, t, g, k, ans;while(scanf("%d", &n)&&n){scanf("%d", &g);n--; //因為后面要創造一個新的數列，相比之下會比之前的少一項for(t=0; t<n; ++t){scanf("%d", &k); //作差，創造一個新的數列，因為最長的重復子串里（假設長度為n)，就會有n-1個差值一一對應相等（重復的與前面的比較）a[t]=k-g+88; //這樣就可以把題目轉化成求不可重疊的最長重復子串g=k;}a[n]=0; //末尾再加一項最小的da(a, sa, n+1, 180);calheight(a, sa, n);int l=0, r=n, mid;ans=0; while(l<=r) //二分法來推滿足的長度{mid=(l+r)>>1;if(check(mid, n)) //看看還可不可以深入{ans=mid;l=mid+1;}else r=mid-1;}if(ans<4) {printf("0\n");}else printf("%d\n", ans+1); //因為這是一個新的通過作差構造出來的數列，所以個數要+1}return 0; }

?

總結

以上是生活随笔為你收集整理的Musical Theme的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。