记录编号	382265	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015]最短不公共子串	最终得分	100
用户昵称	ONCE AGAIN	是否通过	通过
代码语言	C++	运行时间	0.174 s
提交时间	2017-03-13 16:33:34	内存使用	63.38 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int SIZEN = 4010;
char s1[SIZEN]={0},s2[SIZEN]={0};
int len1,len2;
struct Suffix_AutoMaton{
	int ch[SIZEN][26];
	int fail[SIZEN];
	int val[SIZEN];
	int sum[SIZEN];
	int ws[SIZEN];
	int Rank[SIZEN];
	int node,now,temp;
	Suffix_AutoMaton(){node = now = 1;memset(sum,0,sizeof sum);}
	
	int NewNode(int v,int f){
		val[++node] = v;
		fail[node] = f;
		return node;
	}
	
	void add(int c){
		int curnode =NewNode(val[now]+1,0);
		for(temp=now;temp&&!ch[temp][c];temp=fail[temp])ch[temp][c]=curnode;
		if(!temp)fail[curnode] = 1;
		else{
			int p = ch[temp][c];
			if(val[p] == val[temp]+1)fail[curnode] = p;
			else{
				int newnode = NewNode(val[temp]+1,fail[p]);
				memcpy(ch[newnode],ch[p],sizeof ch[p]);
				fail[p] = fail[curnode] = newnode;
				for(;temp&&ch[temp][c]==p;temp=fail[temp])ch[temp][c]=newnode;
			}
		}
		now = curnode;
	}
	
	void getrank(){
		for(int i = 1;i <= node;i++)ws[val[i]]++;
		for(int i = 1;i <= node;i++)ws[i] += ws[i-1];
		for(int i = node;i >= 1;i--)Rank[ws[val[i]]--] = i;
	}
	void build(char *r,int n){
		for(int i = 0;i < n;i++)add(r[i]-'a');
		getrank();
	}
	int match(char *r,int n){
		now = 1;int len = 0;
		for(int i = 0;i < n;i++){
			int c = r[i]-'a';
			if(ch[now][c]){now = ch[now][c];len++;}
			else {
				for(;now&&!ch[now][c];now=fail[now]);
				if(!now){now = 1;len = 0;}
				else {len = val[now]+1;now=ch[now][c];}
			}
			sum[now] = max(sum[now],len);
		}
		int ans = 0x3f3f3f3f;
		for(int i = node;i>=1;i--){
			int x = Rank[i];
			sum[fail[x]] = max(min(sum[x],val[fail[x]]),sum[fail[x]]);
		}
		//for(int i = 1;i <= node;i++)printf("%d ",sum[i]);printf("\n");
		//for(int i = 1;i <= node;i++)printf("%d ",val[i]);printf("\n");
		for(int i = 2;i <= node;i++){
			if(sum[i] > val[fail[i]] && sum[i] < val[i])
			ans = min(ans,sum[i]+1);
			if(!sum[i])ans = min(ans,val[fail[i]]+1);
		}
		return ans == 0x3f3f3f3f?-1:ans;
	}
	void Print(){
		printf("Suffix_AutoMaton : \n");
		for(int i = 0;i <= node;i++){
			printf("node = %d :",i);
			for(int j = 0;j < 26;j++)printf("%d ",ch[i][j]);
			printf("\n");
		}
	}
}A,B;
struct Sequence_AutoMaton{
	int ch[SIZEN][26];
	int near[26];
	int node;
	Sequence_AutoMaton(){memset(ch,0,sizeof ch);}
	void build(char *r,int n){
		for(int i = n;i>=0;i--){
			for(int j = 0;j < 26;j++)ch[i][j] = near[j];
			if(i)near[r[i-1]-'a'] = i;
		}
		node = n;
	}
	int match(char *r,int x,int y){
		int now = 0;
		for(int i = x;i <= y;i++){
			int c = r[i]-'a';
			if(ch[now][c])now=ch[now][c];
			else return i-x+1;
		}
		return 0x3f3f3f3f;
	}
	void Print(){
		printf("Sequence_AutoMaton : \n");
		for(int i = 0;i <= node;i++){
			printf("node = %d :",i);
			for(int j = 0;j < 26;j++)printf("%d ",ch[i][j]);
			printf("\n");
		}
	}
}AA,BB;
void SubTeskOne(){
	printf("%d\n",A.match(s2,len2));
}
void SubTeskTwo(){
	int ans = 0x3f3f3f3f;
	for(int i = 0;i < len1;i++)
		ans = min(ans,BB.match(s1,i,len1-1));
	printf("%d\n",ans == 0x3f3f3f3f?-1:ans);
}
bool flag = true;
int F[SIZEN][SIZEN]={0};
void DFS1(int seq,int suf,int x){
	if(!flag||!x)return;
	for(int i = 0;i < 26&&flag;i++){
		if(AA.ch[seq][i]&&B.ch[suf][i])DFS1(AA.ch[seq][i],B.ch[suf][i],x-1);
		else if(AA.ch[seq][i]&&!B.ch[suf][i])flag = false;
	}
}
void SubTeskThree(){
	int l = 1,r = min(len1,len2),mid,ans = 0x3f3f3f3f;
	while(l <= r){
		mid = (l+r)>>1;
		flag = true;
		DFS1(0,1,mid);//Seq Suf
		if(flag == true)l = mid+1;
		else r = mid-1,ans = min(ans,mid);
	}
	printf("%d\n",ans == 0x3f3f3f3f?-1:ans);
}
 
int ans = 0x3f3f3f3f;
void DFS(int now1,int now2,int len){
//	if(len > ans)return;
	if(F[now1][now2]){ans = min(ans,len+F[now1][now2]);return;}
	F[now1][now2] = 0x3f3f3f3f;
	for(int i = 0;i < 26;i++){
		if(!AA.ch[now1][i])continue;
		if(!BB.ch[now2][i]){
			ans = min(ans,len+1);
			F[now1][now2] = 1;
		}
		else {
			DFS(AA.ch[now1][i],BB.ch[now2][i],len+1);
			if(F[AA.ch[now1][i]][BB.ch[now2][i]])
				F[now1][now2] = min(F[now1][now2],F[AA.ch[now1][i]][BB.ch[now2][i]]+1);
		}
	}
}
void SubTeskFour(){
	DFS(0,0,0);
	printf("%d\n",ans == 0x3f3f3f3f?-1:ans);
}
int main(){
	freopen("sus.in","r",stdin);
	freopen("sus.out","w",stdout);
	scanf("%s%s",s1,s2);
	len1 = strlen(s1),len2 = strlen(s2);
	//printf("%d %d\n",len1,len2);
	A.build(s1,len1);B.build(s2,len2);
	AA.build(s1,len1);BB.build(s2,len2);
	//AA.Print();
	//B.Print();
	SubTeskOne();
	SubTeskTwo();
	SubTeskThree();
	SubTeskFour();
	return 0;
}