因为只有三个字符串，所以就有一个比较暴力的做法：枚举这三个串所有排列，然后对于每一个排列，减去这三个串两两的公共部分的长度，更新答案。
求公共部分自然想到kmp：比如s[1]接在s[0]后面，那么我们只用把s[0]和s[1]匹配，把s[1]当做模式串，s[0]当做文本串，当s[0]匹配到头的时候，看s[1]匹配到哪，就是这两个串的公共长度。
那么就会有s[1]是s[0]的子串的情况，这时候只记录s[0[的长度，然后再减去s[0]和s[2]的公共长度（我就是因为刚开始忘减了wa了几发）。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 char s[3][maxn]; 38 int len[3], f[3][maxn], kmp[3][3]; 39 40 void init(int m, char *s, int id) 41 { 42 f[id][1] = 0; 43 for(int i = 2, j = 0; i <= m; ++i) 44 { 45 while(s[j + 1] != s[i] && j) j = f[id][j]; 46 if(s[j + 1] == s[i]) j++; 47 f[id][i] = j; 48 } 49 } 50 int KMP(int n, int m, char *s1, char *s2, int id) 51 { 52 int j = 0; 53 for(int i = 1; i <= n; ++i) 54 { 55 while(s2[j + 1] != s1[i] && j) j = f[id][j]; 56 if(s2[j + 1] == s1[i]) j++; 57 if(j == m) return -1; 58 } 59 return j; 60 } 61 62 int main() 63 { 64 scanf("%s%s%s", s[0] + 1, s[1] + 1, s[2] + 1); 65 int ans = INF; 66 for(int i = 0; i < 3; ++i) len[i] = strlen(s[i] + 1); 67 for(int i = 0; i < 3; ++i) 68 { 69 init(len[i], s[i], i); 70 for(int j = 0; j < 3; ++j) if(i != j) 71 kmp[j][i] = KMP(len[j], len[i], s[j], s[i], i); 72 //这时候要把i作为文本串，因为j的fail数组还没构造 73 } 74 for(int i = 0; i < 3; ++i) 75 for(int j = 0; j < 3; ++j) 76 for(int k = 0; k < 3; ++k) 77 { 78 if(i == j || j == k || i == k) continue; 79 int sum = len[i] + len[j] + len[k] - kmp[i][j] - kmp[j][k]; 80 if(kmp[i][j] >= 0) 81 { 82 if(kmp[j][k] >= 0) ans = min(ans, sum); 83 else ans = min(ans, sum - len[k] - 1); 84 } 85 else 86 { 87 if(kmp[j][k] >= 0) ans = min(ans, sum - len[j] - 1 + kmp[j][k] - kmp[i][k]);//别忘了 88 else ans = min(ans, len[i]); 89 } 90 } 91 write(ans); enter; 92 return 0; 93 }