【题目链接】
【题意】
求不可重叠最长重复子串。
2015-11-27
【思路】
1) 据题意处理字符串
2) 后缀数组。二分长度k，问题成为了判定是否存在两个及以上长度不小于k且互不重叠的子串。根据height数组划分后缀，满足两个条件：一是一组内height值不小于k（保证组内任两个长度不小于k即存在长度不小于k的子串），二是组内后缀sa值的最大最小值之差大于等于k（保证两个子串不重叠）。
需要注意n==1时需要特判。
1/为什么可以划分height数组呢？首先height[i]代表lcp(suffix(sa[i]),suffix(sa[i-1]))，所以height所对应的后缀是有序的，如果划分出现height<k的话以后的后缀与改组内的lcp一定不大于k-1，所以不会出现后面的再划分到改组的情况。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int maxn = +; int s[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn],n; void build_sa(int m) {
int i,*x=t,*y=t2;
for(int i=;i<m;i++) c[i]=;
for(int i=;i<n;i++) c[x[i]=s[i]]++;
for(int i=;i<m;i++) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[i]]]=i; for(int k=;k<=n;k<<=) {
int p=;
for(int i=n-k;i<n;i++) y[p++]=i;
for(int i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; for(int i=;i<m;i++) c[i]=;
for(int i=;i<n;i++) c[x[y[i]]]++;
for(int i=;i<m;i++) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y);
p=; x[sa[]]=;
for(int i=;i<n;i++)
x[sa[i]]=y[sa[i-]]==y[sa[i]] && y[sa[i-]+k]==y[sa[i]+k]?p-:p++;
if(p>=n) break;
m=p;
}
} int rank[maxn],height[maxn];
void getHeight() {
int i,j,k=;
for(int i=;i<n;i++) rank[sa[i]]=i;
for(int i=;i<n;i++) {
if(k) k--;
int j=sa[rank[i]-];
while(s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
} bool can(int k) {
int min=sa[],max=sa[];
for(int i=;i<n;i++) {
if(height[i]<k) min=max=sa[i];
if(sa[i]<min) min=sa[i];
if(sa[i]>max) max=sa[i];
if(max-min>=k) return true;
}
return false;
} int main() {
while(scanf("%d",&n)== && n)
{
for(int i=;i<n;i++)scanf("%d",&s[i]);
for(int i=n-;i>;i--)s[i]=s[i]-s[i-]+;
n--;
for(int i=;i<n;i++)s[i]=s[i+];
s[n]=;
build_sa();
getHeight();
int L=,R=n/;
while(L<R) {
int M=L+(R-L+)/;
if(can(M)) L=M; else R=M-;
}
L++;
if(L<=) printf("0\n");
else printf("%d\n",L);
}
return ;
}
2016-2-19
【思路】
SAM+DP
处理出right集的最大值mx和最小值mn，即该状态对应所有字符串的结束位置的最大与最小，递推式为：
mx[p]=max{ l[p], mx[np],np->fa=p }
mn[p]=min{ l[p], mn[np],np->fa=p }
则状态i对应字符串中的最长重复子串的长度为min{l[i],mx[i]-mn[i]}，可以拿个栗子自己看一下，这样保证了不重叠。然后取所有状态的最大值即可。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int N = *1e4+;
const int sigma = ; int s[N/];
int root,last,sz,ch[N][sigma],fa[N],l[N],mn[N],mx[N];
int b[N],cnt[N],n; void init() {
sz=; root=last=++sz;
memset(fa,,sizeof(fa));
memset(mx,,sizeof(mx));
memset(mn,,sizeof(mn));
memset(cnt,,sizeof(cnt));
memset(ch,,sizeof(ch));
}
void add(int x) {
int c=s[x];
int p=last,np=++sz; last=np;
mn[np]=mx[np]=l[np]=x;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=root;
else {
int q=ch[p][c];
if(l[p]+==l[q]) fa[np]=q;
else {
int nq=++sz; l[nq]=l[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];
fa[np]=fa[q]=nq;
for(;p&&q==ch[p][c];p=fa[p]) ch[p][c]=nq;
}
}
}
void solve() {
for(int i=;i<=sz;i++) cnt[l[i]]++;
for(int i=;i<=n;i++) cnt[i]+=cnt[i-];
for(int i=;i<=sz;i++) b[cnt[l[i]]--]=i;
int ans=;
for(int i=sz;i;i--) {
int p=b[i];
if(fa[p]) {
if(mn[fa[p]]>mn[p]) mn[fa[p]]=mn[p];
if(mx[fa[p]]<mx[p]) mx[fa[p]]=mx[p];
}
}
for(int i=;i<=sz;i++)
ans=max(ans,min(l[i],mx[i]-mn[i]));
if(ans<) puts("");
else printf("%d\n",ans+);
}
void read(int& x) {
char c=getchar(); int f=; x=;
while(!isdigit(c)){if(c=='-')f=-;c=getchar();}
while(isdigit(c)) x=x*+c-'',c=getchar();
x*=f;
} int main() {
while(read(n),n) {
init();
for(int i=;i<=n;i++) read(s[i]); n--;
for(int i=;i<=n;i++) s[i]=s[i+]-s[i]+,add(i);
solve();
}
return ;
}