记录编号	392183	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015]最短不公共子串	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.004 s
提交时间	2017-04-07 14:02:34	内存使用	97.08 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5010;
char s[N],t[N];
int n,m,last,top,par[N],len[N],go[N][26];
int New(int L){len[++top]=L;return top;}
void extend(int w){
	int p=last,np=New(len[p]+1);
	while (p&&!go[p][w]) go[p][w]=np,p=par[p];
	if (!p) par[np]=1;
	else{
		int q=go[p][w];
		if (len[q]==len[p]+1) par[np]=q;
		else{
			int nq=New(len[p]+1);
			memcpy(go[nq],go[q],sizeof go[q]);
			par[nq]=par[q];
			par[np]=par[q]=nq;
			while (p&&go[p][w]==q) go[p][w]=nq,p=par[p];
		}
	}
	last=np;
}
void solve1(){
	int ans=1e9;
	for (int i=1;i<=n;i++){
		int p=1,j=i;
		for (;p&&j<=n;j++) p=go[p][s[j]];
		if (!p) ans=min(ans,j-i);
	}
	printf("%d\n",ans<1e9?ans:-1);
}
int next[N][26];//next[i][w]表示t[i]后面最近的w的位置 
void solve2(){
	int ans=1e9;
	for (int i=1;i<=n;i++){
		int p=0,j=i;
		for (;p!=-1&&j<=n;j++) p=next[p][s[j]];
		if (p==-1) ans=min(ans,j-i);
	}
	printf("%d\n",ans<1e9?ans:-1);
}
int dp[N][N];
void solve3(){
	//dp[i][j]表示用到S[i],走到B的j状态,最短长度 
	memset(dp,0x3f,sizeof dp);
	dp[0][1]=0;
	for (int i=0;i<n;i++)
	for (int j=0;j<=top;j++){
		dp[i+1][j]=min(dp[i+1][j],dp[i][j]);//不取s[i+1] 
		int p=go[j][s[i+1]];//取s[i+1] 
		dp[i+1][p]=min(dp[i+1][p],dp[i][j]+1);
	}
	printf("%d\n",dp[n][0]<1e9?dp[n][0]:-1);
}
void solve4(){
	//dp[i][j]表示用到S[i],T[j]时的最短长度 
	memset(dp,0x3f,sizeof dp);
	dp[0][0]=0;
	int ans=1e9;
	for (int i=0;i<n;i++)
	for (int j=0;j<=m;j++){
		dp[i+1][j]=min(dp[i+1][j],dp[i][j]);//不取s[i] 
		int p=next[j][s[i+1]];//取s[i+1] 
		if (p==-1) ans=min(ans,dp[i][j]+1);
			else dp[i+1][p]=min(dp[i+1][p],dp[i][j]+1);
	}
	printf("%d\n",ans<1e9?ans:-1);
}
int main()
{
	freopen("sus.in","r",stdin);
	freopen("sus.out","w",stdout);
	scanf("%s%s",s+1,t+1);
	n=strlen(s+1);
	m=strlen(t+1);
	last=New(0);
	for (int i=1;i<=n;i++) s[i]-='a';
	for (int i=1;i<=m;i++) extend(t[i]-='a');
	memset(next,-1,sizeof next);
	for (int i=m-1;i>=0;i--){
		for (int j=0;j<26;j++) next[i][j]=next[i+1][j];
		next[i][t[i+1]]=i+1;
	}
	solve1();
	solve2();
	solve3();
	solve4();
	return 0;
}