25 E Test

問題

文字列s1,s2,s3が与えられる。
s1,s2,s3を（連続する）部分文字列として含むような、長さ最小の文字列の長さを求めよ。

制約条件

s1,s2,s3の長さ≦10^5

方針

文字列A,Bを部分文字列として含む長さ最小の文字列は、

• AがBに含まれる、またはBがAに含まれる場合、AあるいはBそのもの
• そうでないとき、Aの末尾i文字とBの先頭i文字が一致する場合、それを重ねたもの

なので、s1,s2,s3を、最大何字末尾と先頭が重なるかを見てやればよい。
これはナイーブにやるとO(n^2)かかってTLEになるが、
rolling hashを使えばO(n)になるので通る。

rolling hashは何回か書いたが、文字列sをc1,c2,c3,c4,...,cnとするとき、
c1c2c3c4...cnを27進法の数字として見た値のことである。

ソースコード

string in[3];
ll ha[200001],hb[200001];
string merge(string &a,string &b){
	int la=a.size(), lb=b.size(), ret=0;
	ll tmp;
	
	if(la>=lb){
		ha[0]=hb[0]=0;
		tmp=1; rep(i,la)ha[i+1]=ha[i]+(a[i]-'a')*tmp, tmp*=29;
		tmp=1; rep(i,lb)hb[i+1]=hb[i]+(b[i]-'a')*tmp, tmp*=29;
		
		tmp=hb[lb];
		for(int i=lb;i<=la;i++){
			if(ha[i]-ha[i-lb]==tmp)return a;
			tmp*=29;
		}
	}
	
	ha[la]=hb[0]=0;
	rep(i,la)ha[la-i-1]=ha[la-i]*29+(a[la-i-1]-'a');
	tmp=1; rep(i,lb)hb[i+1]=hb[i]+(b[i]-'a')*tmp, tmp*=29;
	
	for(int i=1;i<=min(la,lb);i++){
		if(ha[la-i]==hb[i])ret=i;
	}
	return a.substr(0,la-ret)+b;
}

void run()
{
	rep(i,3)cin>>in[i];
	sort(in,in+3);
	int ans=1e9;
	do{
		string a,b;
		a=merge(in[0],in[1]);
		b=merge(a,in[2]);
		ans=min(ans,(int)b.size());
	}while(next_permutation(in,in+3));
	
	cout<<ans<<endl;
}