BZOJ4032 : [HEOI2015]最短不公共子串

第一问:

对B串建立SAM,暴力枚举A的每个子串,在SAM上走,若失配则可行。

第二问:

设g[i][j]表示B串的第i个字符之后最早出现的字符j的位置,暴力枚举A的每个子串,按照g贪心地走,若失配则可行。

第三问:

对B串建立SAM,设f[i][j]表示考虑了A的前i个字符,当前在SAM上的状态为j的最小长度,然后DP。

第四问:

设g[i][j]表示B串的第i个字符之后最早出现的字符j的位置,f[i][j]表示考虑了A的前i个字符,当前在g[]中匹配到了j的最小长度,然后DP。

时间复杂度$O(n^2)$。

#include<cstdio>
#include<cstring>
const int N=2010,S=26;
int n,m,i,j,x,ans1=N,ans2=N,ans3=N,ans4=N;char a[N],b[N];
inline void up(int&a,int b){if(a>b)a=b;}
namespace String{
int tot=1,last=1,pre[N<<1],son[N<<1][S],ml[N<<1],f[N][N<<1];
inline void extend(int w){
int p=++tot,x=last,r,q;
for(ml[last=p]=ml[x]+1;x&&!son[x][w];x=pre[x])son[x][w]=p;
if(!x)pre[p]=1;
else if(ml[x]+1==ml[q=son[x][w]])pre[p]=q;
else{
pre[r=++tot]=pre[q];std::memcpy(son[r],son[q],sizeof son[r]);
ml[r]=ml[x]+1;pre[p]=pre[q]=r;
for(;x&&son[x][w]==q;x=pre[x])son[x][w]=r;
}
}
void work(){
for(i=1;i<=m;i++)extend(b[i]);
for(i=1;i<=n;i++)for(x=1,j=i;j<=n&&j-i+1<ans1;j++){
x=son[x][a[j]];
if(!x)ans1=j-i+1;
}
for(i=0;i<=n;i++)for(j=1;j<=tot;j++)f[i][j]=N;
for(f[0][1]=i=0;i<n;i++)for(j=1;j<=tot;j++)if(f[i][j]<N){
up(f[i+1][j],f[i][j]);
if(son[j][a[i+1]])up(f[i+1][son[j][a[i+1]]],f[i][j]+1);else up(ans3,f[i][j]+1);
}
}
}
namespace Sequence{
int g[N][S],f[N][N];
void work(){
for(j=0;j<S;j++)g[m][j]=-1;
for(i=m;i;i--)for(j=0;j<S;j++)if(b[i]==j)g[i-1][j]=i;else g[i-1][j]=g[i][j];
for(i=1;i<=n;i++)for(x=0,j=i;j<=n&&j-i+1<ans2;j++){
x=g[x][a[j]];
if(x<0)ans2=j-i+1;
}
for(i=0;i<=n;i++)for(j=0;j<=m;j++)f[i][j]=N;
for(f[0][0]=i=0;i<n;i++)for(j=0;j<=m;j++)if(f[i][j]<N){
up(f[i+1][j],f[i][j]);
if(~g[j][a[i+1]])up(f[i+1][g[j][a[i+1]]],f[i][j]+1);else up(ans4,f[i][j]+1);
}
}
}
int main(){
scanf("%s%s",a+1,b+1),n=strlen(a+1),m=strlen(b+1);
for(i=1;i<=n;i++)a[i]-='a';
for(i=1;i<=m;i++)b[i]-='a';
String::work();
Sequence::work();
if(ans1==N)ans1=-1;
if(ans2==N)ans2=-1;
if(ans3==N)ans3=-1;
if(ans4==N)ans4=-1;
return printf("%d\n%d\n%d\n%d",ans1,ans2,ans3,ans4),0;
}

  

上一篇:ABP之模块分析


下一篇:【fhq Treap】bzoj1500(听说此题多码上几遍就能不惧任何平衡树题)