KMP玄关求调
  • 板块CF25E Test
  • 楼主Jadonyzx
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/2 16:34
  • 上次更新2024/6/2 18:43:44
查看原帖
KMP玄关求调
1164775
Jadonyzx楼主2024/6/2 16:34
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
string s13,s23,s33;
char s1[maxn],s2[maxn],s3[maxn];
int len1,len2,len3;
int border1[maxn],border2[maxn],border3[maxn],now;
int sum,ans,L1,L2,L3,L21,L12,L31,L13,L32,L23;
void init(){len1=L1;len2=L2;len3=L3;return;}
void findborder(){
	now=0;
	for(int i=2;i<=len1;++i){
		if(s1[i]==s1[now+1])border1[i]=++now;
		else{
			if(now==0){border1[i]=0;continue;}
			now=border1[now];i--;
		}
	}
	now=0;
	for(int i=2;i<=len2;++i){
		if(s2[i]==s2[now+1])border2[i]=++now;
		else{
			if(now==0){border2[i]=0;continue;}
			now=border2[now];i--;
		}
	}
	now=0;
	for(int i=2;i<=len3;++i){
		if(s3[i]==s3[now+1])border3[i]=++now;
		else{
			if(now==0){border3[i]=0;continue;}
			now=border3[now];i--;
		}
	}
	return;
}
void find(){
	int i=1;int j=0;
	while(i<=len2){
		for(;j<min(len1,len2-i+1);++j)if(s1[j+1]!=s2[j+i]){break;}
		if(j==min(len1,len2-i+1)){break;}
		if(j==0)i++;
		else{i+=j-border1[j];j=border1[j];}
	}
	L21=i+1;
	i=1;j=0;
	while(i<=len1){
		for(;j<min(len2,len1-i+1);++j)if(s2[j+1]!=s1[j+i]){break;}
		if(j==min(len2,len1-i+1)){break;}
		if(j==0)i++;
		else{i+=j-border2[j];j=border2[j];}
	}
	L12=i+1;
	i=1;j=0;
	while(i<=len3){
		for(;j<min(len1,len3-i+1);++j)if(s1[j+1]!=s3[j+i]){break;}
		if(j==min(len1,len3-i+1)){break;}
		if(j==0)i++;
		else{i+=j-border1[j];j=border1[j];}
	}
	L31=i+1;
	i=1;j=0;
	while(i<=len1){
		for(;j<min(len3,len1-i+1);++j)if(s3[j+1]!=s1[j+i]){break;}
		if(j==min(len3,len1-i+1)){break;}
		if(j==0)i++;
		else{i+=j-border3[j];j=border3[j];}
	}
	L13=i+1;
	i=1;j=0;
	while(i<=len3){
		for(;j<min(len2,len3-i+1);++j)if(s2[j+1]!=s3[j+i]){break;}
		if(j==min(len2,len3-i+1)){break;}
		if(j==0)i++;
		else{i+=j-border2[j];j=border2[j];}
	}
	L32=i+1;
	i=1;j=0;
	while(i<=len2){
		for(;j<min(len3,len2-i+1);++j)if(s3[j+1]!=s2[j+i]){break;}
		if(j==min(len3,len2-i+1)){break;}
		if(j==0)i++;
		else{i+=j-border3[j];j=border3[j];}
	}
	L23=i+1;
	L12=min(len1,max(0,L12));
	L13=min(len1,max(0,L13));
	L23=min(len2,max(0,L23));
	L21=min(len2,max(0,L21));
	L31=min(len3,max(0,L31));
	L32=min(len3,max(0,L32));
	return;
}
signed main(){
	cin>>(s13)>>(s23)>>(s33);
	len1=s13.size();
	len2=s23.size();
	len3=s33.size();
	for(int i=1;i<=len1;++i)s1[i]=s13[i-1];
	for(int i=1;i<=len2;++i)s2[i]=s23[i-1];
	for(int i=1;i<=len3;++i)s3[i]=s23[i-1];
	findborder();sum=len1+len2+len3;L1=len1;L2=len2;L3=len3;
	find();
	ans=sum;
	cout<<"1-2:"<<L12<<" 1-3:"<<L13<<" 2-1:"<<L21<<" 2-3:"<<L23<<" 3-1:"<<L31<<" 3-2:"<<L32<<'\n';
	ans=min(ans,L12+L23);//123
	ans=min(ans,L13+L32);//132
	ans=min(ans,L21+L13);//213
	ans=min(ans,L23+L31);//231
	ans=min(ans,L31+L12);//312
	ans=min(ans,L32+L21);//321
	cout<<ans;
	return 0;
}
2024/6/2 16:34
加载中...