原题链接：https://www.luogu.com.cn/problem/CF25E https://codeforces.com/contest/25/problem/E
题意解读：给定a，b，c三个字符串，求包含a、b、c的最短字符串长度。
解题思路：
要得到包含a、b、c的字符串，可以通过a、b、c连接形成，而要使得连接后的字符串最短，可以尽可能的利用重叠部分
如a、b字符串连接的情况可能有三种：连续、交叉、包含
因此，对于a、b字符串连接的最短长度，可以先计算a是否包含b，如果包含b，连接后的长度即a的长度；再计算a后缀与b前缀公共长度ab，连接后长度为a.size()+b.size()-ab。
而a、b、c连接的方式一共有六种：
a->b->c
a->c->b
b->a->c
b->c->a
c->a->b
c->b->a
枚举所有情况下连接后得到的字符串长度，取最短即可。
这里有一个关键函数：int longest(string &x, string &y)
用来计算x后缀与y前缀的最长公共长度，且如果x包含y函数返回-1
STL String暴力枚举：
int longest(string &x, string &y)
{if(x.find(y) != string::npos) return -1; //如果x包含yint len = min(x.size(), y.size());int res = 0;for(int i = 1; i <= len; i++) //枚举前后缀的公共长度{string post = x.substr(x.size() - i, i); //x的后缀string pre = y.substr(0, i); //y的前缀if(post == pre) res = i; //判断是否相等}return res;
}以上方法是O(n^2)的，必须优化
KMP优化实现：
int longest_kmp(string &x, string &y)
{memset(Next, 0, sizeof(Next));//利用y计算Next数组for(int i = 1, j = 0; i < y.size(); i++){while(j && y[i] != y[j]) j = Next[j - 1];if(y[i] == y[j]) j++;Next[i] = j;}int j = 0;//在x中找y，如果找到返回-1，如果没找到，返回y最后匹配的位置即最大公共前后缀长度for(int i = 0; i < x.size(); i++){while(j && x[i] != y[j]) j = Next[j - 1];if(x[i] == y[j]) j++;if(j == y.size()) return -1;}return j;
}100分代码：
#include <bits/stdc++.h>
using namespace std;string a, b, c;
int Next[100005];//计算相同的x的后缀和y的前缀长度,x包含y时返回-1
int longest(string &x, string &y)
{if(x.find(y) != string::npos) return -1; //如果x包含yint len = min(x.size(), y.size());int res = 0;for(int i = 1; i <= len; i++) //枚举前后缀的公共长度{string post = x.substr(x.size() - i, i); //x的后缀string pre = y.substr(0, i); //y的前缀if(post == pre) res = i; //判断是否相等}return res;
}//用KMP优化上面的longest函数
int longest_kmp(string &x, string &y)
{memset(Next, 0, sizeof(Next));//利用y计算Next数组for(int i = 1, j = 0; i < y.size(); i++){while(j && y[i] != y[j]) j = Next[j - 1];if(y[i] == y[j]) j++;Next[i] = j;}int j = 0;//在x中找y，如果找到返回-1，如果没找到，返回y最后匹配的位置即最大公共前后缀长度for(int i = 0; i < x.size(); i++){while(j && x[i] != y[j]) j = Next[j - 1];if(x[i] == y[j]) j++;if(j == y.size()) return -1;}return j;
}//计算x->y->z连接顺序下的最短字符串长度
long long calcu(string &x, string &y, string &z, int xy, int yz, int xz)
{long long res = x.size(); //加上x的长度if(xy >= 0) //如果y不是x的子串{res += y.size() - xy; //加上y的长度，减去y前缀和x后缀重叠部分的长度if(yz >= 0) res += z.size() - yz; //如果z不是y的子串，加上z的长度，减去z前缀和y后缀重叠部分的长度} else //如果y是x的子串{if(xz >= 0) res += z.size() - xz; //如果z不是x的子串，加上z的长度，减去z前缀和x后缀重叠部分的长度}return res;
}int main()
{cin >> a >> b >> c;int ab = longest_kmp(a, b);int ba = longest_kmp(b, a);int bc = longest_kmp(b, c);int cb = longest_kmp(c, b);int ca = longest_kmp(c, a);int ac = longest_kmp(a, c);long long ans = 1e18, t;//abct = calcu(a, b, c, ab, bc, ac);ans = min(ans, t);//acbt = calcu(a, c, b, ac, cb, ab);ans = min(ans, t);//bact = calcu(b, a, c, ba, ac, bc);ans = min(ans, t);//bcat = calcu(b, c, a, bc, ca, ba);ans = min(ans, t);//cabt = calcu(c, a, b ,ca, ab, cb);ans = min(ans, t);//cbat = calcu(c, b, a, cb, ba, ca);ans = min(ans, t);cout << ans;return 0;
}
