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)>=mid
return 1;
}
}
return 0;
}
int main()
{
#ifdef DEBUG
freopen("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 DEBUG
printf("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)>=mid
flag=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;
}
京公网安备 11010502036488号