Description
Sometimes it is hard to prepare tests for programming problems. Now Bob is preparing tests to new problem about strings — input data to his problem is one string. Bob has 3 wrong solutions to this problem. The first gives the wrong answer if the input data contains the substring s1, the second enters an infinite loop if the input data contains the substring s2, and the third requires too much memory if the input data contains the substring s3. Bob wants these solutions to fail single test. What is the minimal length of test, which couldn't be passed by all three Bob's solutions?
Input
There are exactly 3 lines in the input data. The i-th line contains string si. All the strings are non-empty, consists of lowercase Latin letters, the length of each string doesn't exceed 105.
Output
Output one number — what is minimal length of the string, containing s1, s2 and s3
Sample Input
Input
ab
bc
cd
Output
4
Input
abacaba
abaaba
x
Output
11
先用kmp求出各串之間的關系和合并的代價，然後枚舉一遍即可。
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100005;
char s[3][maxn];
int nt[3][maxn];
int flag[3],dis[3][3];
int min(int x,int y)
{
return x < y?x:y;
}
int max(int x,int y)
{
return x > y?x:y;
}
int main()
{
int i,j,k,q,h;
for (i=0;i<3;i++)
{
scanf("%s",s[i]);
dis[i][i]=strlen(s[i]);
}
for (i=0;i<3;i++)
{
nt[i][0]=-1;
for (j=0;s[i][j];j++)
{
int k=nt[i][j];
while (k>=0&&s[i][j]!=s[i][k]) k=nt[i][k];
nt[i][j+1]=k+1;
}
}
for (i=0;i<3;i++)
{
for (j=0;j<3;j++)
{
if (i==j) continue;
for (q=0,h=nt[i][1];s[j][q];)
{
if (h<0||s[j][q]==s[i][h])
{
q++,h++;
if (!s[i][h]) flag[i]=1;
}
else h=nt[i][h];
if (!s[j][q]) dis[j][i]=h;
}
}
}
int ans=0x7FFFFFFF,sum=0,now=0,c=3;
for (i=0;i<3;i++) c-=flag[i];
for (i=0;i<3;i++)
{
if (flag[i]) continue;
sum=dis[i][i];
for (j=0;j<3;j++)
{
if (i==j||flag[j]) continue;
sum+=dis[j][j]-dis[i][j];
for (k=0;k<3;k++)
{
if (k==i||k==j||flag[k]) continue;
sum+=dis[k][k]-dis[j][k];
if (c==3) ans=min(ans,sum);
sum-=dis[k][k]-dis[j][k];
}
if (c==2) ans=min(ans,sum);
sum-=dis[j][j]-dis[i][j];
}
if (c==1) ans=min(ans,sum);
}
if (c==0) ans=max(dis[0][0],max(dis[1][1],dis[2][2]));
printf("%d\n",ans);
return 0;
}