KMP WA on #25求调
  • 板块CF25E Test
  • 楼主toolong114514
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/27 16:22
  • 上次更新2024/6/27 16:36:41
查看原帖
KMP WA on #25求调
477821
toolong114514楼主2024/6/27 16:22
#include<iostream>
#include<cstring>
using namespace std;
const int INF=1e9+10;
const int N=1e6+10;
int nxt1[N],nxt2[N],nxt3[N];
char str1[N],str2[N],str3[N];
int fuck[10][10];
bool incl[10][10];
int len1,len2,len3;
int ans=INF;
int main(){
	ios::sync_with_stdio(false);
	cin>>str1;
	cin>>str2;
	cin>>str3;
	len1=strlen(str1);len2=strlen(str2);len3=strlen(str3);
	//cout<<len1<<" "<<len2<<" "<<len3<<endl;
	int j=-1;
	nxt1[0]=nxt2[0]=nxt3[0]=-1;
	for(int i=1;i<len1;i++){
		while(j!=-1&&str1[j+1]!=str1[i]) j=nxt1[j];
		if(str1[j+1]==str1[i]) j++;
		nxt1[i]=j;
	}
	j=-1;
	for(int i=1;i<len2;i++){
		while(j!=-1&&str2[j+1]!=str2[i]) j=nxt2[j];
		if(str2[j+1]==str2[i]) j++;
		nxt2[i]=j;
	}
	j=-1;
	for(int i=1;i<len3;i++){
		while(j!=-1&&str3[j+1]!=str3[i]) j=nxt3[j];
		if(str3[j+1]==str3[i]) j++;
		nxt3[i]=j;
	}
	//str1<-str2
	j=-1;
	for(int i=0;i<len1;i++){
		while(j!=-1&&str2[j+1]!=str1[i]) j=nxt2[j];
		if(str2[j+1]==str1[i]) j++;
		if(j==len2-1) incl[1][2]=true;
	}
	fuck[1][2]=j+1;
	//str1<-str3
	for(int i=0;i<len1;i++){
		while(j!=-1&&str3[j+1]!=str1[i]) j=nxt3[j];
		if(str3[j+1]==str1[i]) j++;
		if(j==len3-1) incl[1][3]=true;
	}
	fuck[1][3]=j+1;
	//str2<-str1
	j=-1;
	for(int i=0;i<len2;i++){
		while(j!=-1&&str1[j+1]!=str2[i]) j=nxt1[j];
		if(str1[j+1]==str2[i]) j++;
		if(j==len1-1) incl[2][1]=true;
	}
	fuck[2][1]=j+1;	
	//str2<-str3
	j=-1;
	for(int i=0;i<len2;i++){
		while(j!=-1&&str3[j+1]!=str2[i]) j=nxt3[j];
		if(str3[j+1]==str2[i]) j++;
		if(j==len3-1) incl[2][3]=true;
	}
	fuck[2][3]=j+1;	
	//str3<-str1
	j=-1;
	for(int i=0;i<len3;i++){
		while(j!=-1&&str1[j+1]!=str3[i]) j=nxt1[j];
		if(str1[j+1]==str3[i]) j++;
		if(j==len1-1) incl[3][1]=true;
	}
	fuck[3][1]=j+1;
	//str3<-str2
	j=-1;
	for(int i=0;i<len3;i++){
		while(j!=-1&&str2[j+1]!=str3[i]) j=nxt2[j];
		if(str2[j+1]==str3[i]) j++;
		if(j==len2-1) incl[3][2]=true;
	}
	fuck[3][2]=j+1;
//	for(int t1=1;t1<=3;t1++){
//		for(int t2=1;t2<=3;t2++){
//			if(t1==t2) continue;
//			cout<<t1<<" "<<t2<<" "<<fuck[t1][t2]<<endl;
//		}
//	}
	//cout<<"----------\n";
	for(int t1=1;t1<=3;t1++){
		for(int t2=1;t2<=3;t2++){
			for(int t3=1;t3<=3;t3++){
				if(t1==t2||t2==t3||t1==t3) continue;
				//cout<<t1<<" "<<t2<<" "<<t3<<endl;
				//cout<<len1<<" "<<len2<<" "<<len3<<" "<<fuck[t1][t2]<<" "<<fuck[t2][t3]<<endl;
				//cout<<t1<<" "<<t2<<" "<<incl[t1][t2]<<endl;
				if(incl[t1][t2]){
					if(t2==1) ans=min(ans,min(len2+len3-fuck[2][3],len2+len3-fuck[3][2]));
					if(t2==2) ans=min(ans,min(len1+len3-fuck[1][3],len1+len3-fuck[3][1]));
					if(t2==3) ans=min(ans,min(len1+len2-fuck[1][2],len1+len2-fuck[2][1]));
				}else{
					//cout<<len1<<" "<<len2<<" "<<len3<<" "<<fuck[t1][t2]<<" "<<fuck[t2][t3]<<endl;
					ans=min(ans,len1+len2+len3-fuck[t1][t2]-fuck[t2][t3]);
				}
				//cout<<ans<<endl;
			}
		}
	}
	if(incl[1][2]&&incl[1][3]) ans=min(ans,len1);
	if(incl[2][3]&&incl[2][1]) ans=min(ans,len2);
	if(incl[3][1]&&incl[3][2]) ans=min(ans,len3);
	cout<<ans;
	return 0;
}
2024/6/27 16:22
加载中...