[HEOI2015]最短不公共子串

C++11(clang++ 3.9) 解法, 执行用时: 94ms, 内存消耗: 988K, 提交时间: 2019-03-16 14:34:27

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e3+5;
int n,_n;
char a[MAX],b[MAX];
struct SAM{
	int l,r,L;
	int len[MAX],fa[MAX],f[MAX];
	int son[MAX][26],nxt[MAX][26];
	SAM() {l=r=1;}
	void ins(int x)
	{
		int tt=r;
		len[r=++l]=++L;
		for(;tt&&!son[tt][x];tt=fa[tt])
		  son[tt][x]=r;
		if(!tt) return void(fa[r]=1);
		int qwq=son[tt][x];
		if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
		len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
		for(int i=0;i<26;++i)
		  son[l][i]=son[qwq][i];
		for(int i=tt;son[i][x]==qwq;i=fa[i])
		  son[i][x]=l;
	}
	void Solve()
	{
		int ans=1e9;
		for(int i=1,N;i<=n;++i)
		  {
		  	N=min(i+ans-1,n);
		  	for(int j=i,x=1;j<=N;++j)
		  	  {
		  	  	x=son[x][a[j]-'a'];
		  	  	if(!x) {ans=j-i+1;break;}
			  }
		  }
		printf("%d\n",ans==1e9?-1:ans);
	}
	void Solve_()
	{
		int ans=1e9;
		for(int i=0;i<_n;++i)
		  for(int j=i+1;j<=_n;++j)
		    if(!nxt[i][b[j]-'a']) nxt[i][b[j]-'a']=j;
		for(int i=1,N;i<=n;++i)
		  {
		  	N=min(i+ans-1,n);
		  	for(int j=i,x=0;j<=N;++j)
		  	  {
		  	  	x=nxt[x][a[j]-'a'];
		  	  	if(!x) {ans=j-i+1;break;}
			  }
		  }
		printf("%d\n",ans==1e9?-1:ans);
	}
	void Solve__()
	{
		int ans=1e6;
		memset(f,1,sizeof(f));
		f[1]=0;
		for(int i=1;i<=n;++i)
		  for(int j=1,x;j<=l;++j)
		    {
		    	x=son[j][a[i]-'a'];
		    	if(!x) ans=min(ans,f[j]+1);
		    	else f[x]=min(f[x],f[j]+1);
			}
		printf("%d\n",ans==1e6?-1:ans);
	}
	void Solve___()
	{
		int ans=1e6;
		memset(f,1,sizeof(f));
		f[0]=0;
		for(int i=1;i<=n;++i)
		  for(int j=_n,x;j>=0;--j)
		    {
		    	x=nxt[j][a[i]-'a'];
		    	if(!x) ans=min(ans,f[j]+1);
		    	else f[x]=min(f[x],f[j]+1);
			}
		printf("%d\n",ans==1e6?-1:ans);
	}
}_S;
int main()
{
	scanf("%s%s",a+1,b+1),n=strlen(a+1),_n=strlen(b+1);
	for(int i=1;i<=_n;++i)
	  _S.ins(b[i]-'a');
	return _S.Solve(),_S.Solve_(),_S.Solve__(),_S.Solve___(),0;
}

C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 17456K, 提交时间: 2020-08-02 17:55:18

#include "bits/stdc++.h"
using namespace std;

const int maxn = 4e3+10;

struct P{ int a, b, c; };
int ch[2][2][maxn][26], fa[2][maxn], len[2][maxn];
bool vis[maxn][maxn];
int tot[2]={1,1}, last[2]={1,1};
char s[maxn];

void add(int c, int f) {
    int p=last[f], np=last[f]=++tot[f];
    len[f][np]=len[f][p]+1;
    for(; p&&!ch[f][1][p][c]; p=fa[f][p]) ch[f][1][p][c]=np;
    if(!p) fa[f][np]=1;
    else {
        int q=ch[f][1][p][c];
        if(len[f][q]==len[f][p]+1) fa[f][np]=q;
        else {
            int nq=++tot[f]; len[f][nq]=len[f][p]+1;
            fa[f][nq]=fa[f][q]; fa[f][q]=fa[f][np]=nq;
            memcpy(ch[f][1][nq],ch[f][1][q],104);
            for(; p&&ch[f][1][p][c]==q; p=fa[f][p]) ch[f][1][p][c]=nq;
        }
    }
}

void pre(int f) {
    for(int i=strlen(s+1); i; --i) {
        memcpy(ch[f][0][i-1],ch[f][0][i],104);
        ch[f][0][i-1][s[i]-'a']=i;
    }
}

void bfs(int f1, int f2) {
    memset(vis,0,sizeof(vis));
    queue<P> q;
    q.push((P){f1,f2,0}); vis[f1][f2]=1;
    while(!q.empty()) {
        P now=q.front(); q.pop();
        for(int i=0; i<26; ++i) if(ch[0][f1][now.a][i]) {
            if(ch[1][f2][now.b][i]) {
                int a=ch[0][f1][now.a][i], b=ch[1][f2][now.b][i];
                if(!vis[a][b]) vis[a][b]=1, q.push((P){a,b,now.c+1});
            }
            else return (void)printf("%d\n", now.c+1);
        }
    }
    printf("-1\n");
}

int main() {
    scanf("%s", s+1);
    pre(0); for(int i=1; s[i]; ++i) add(s[i]-'a',0);
    scanf("%s", s+1);
    pre(1); for(int i=1; s[i]; ++i) add(s[i]-'a',1);
    bfs(1,1); bfs(1,0); bfs(0,1); bfs(0,0);
}

详情