因为重合部分越短，每次增加的长度就越长，所以如果有多种连接方式，就选择重合部分最短的那一类。
因为要多次判断重合部分的长度，所以可以在dfs之前先预处理打表一遍所有字符串相互的重合长度。
#include <iostream> #include <algorithm> #include <stdlib.h> #include <cstring> #include <vector> using namespace std; const int N = 25; int n, ans, cnt[N]; string s[N]; int check(string a, string b, int lena, int lenb) // a是倒着，b是顺序 { int l = min(lena, lenb); int i; int ans; for (i = 1; i < l; i++) { bool flag = 1; for (int j = 0; j < i; j++) if (a[lena - i + j] != b[j]) { flag = false; break; } if (flag) { return i; } } return 0; } void dfs(int u, int now) { bool flag = false; ans = max(ans, now); for (int i = 1; i <= n; i++) { if (cnt[i] >= 2) continue; int lena = s[u].length(), lenb = s[i].length(); int tmp = check(s[u], s[i], lena, lenb); if (tmp < 1) continue; flag = true; cnt[i]++; dfs(i, now + lenb - tmp); cnt[i]--; } if (!flag) { return; } } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> s[i]; cin >> s[0]; s[0] = " " + s[0]; dfs(0, 1); cout << ans << endl; return 0; }