题目原文
近日刷题，遇到这道题目时思路较混乱，而网上找到的题解代码没有注释，很难理解别人的思路。然后今天想了一个早上，下午AC了，于是决定写一下解析，给日后有需要的人。
题意
当一个字符串的尾部与另一个串的头部重叠时，重叠部分可以合并。程序要求求出合并所了有子串后的最短串长度。
思路
由于每个测试样例的字符串个数N最大为7，所以可以直接暴力搜索。将所有给出的字符串全排列，然后重点是：当两个字串排列在一起时，要将他们首尾重叠部分合并(样例可以参考题目原文)，再将得到的新串继续合并。每合并N次后即可得到一个答案串，然后不断更新最小值即可。
代码(用G++提交可以AC)
#include <iostream>
#include <vector>
#define REP(i, a, b) \for(int i = (int)(a); i < (int)(b); ++i)
using namespace std;
vector<string> v(10);
int book[10000], min_len, n;
string merge(string s1, string s2)//合并字符串
{
int max = 0, index = -1;REP(i, 0, s1.length())//S1从头开始扫描，直到遇到与S2尾部重叠的字符 if(s1[i] == s2[0]){
int x = i, y = 0, len = 0;while(s1[x++] == s2[y++])//计算重叠串长度 {
len++;if(x == s1.length() || y == s2.length())break;}//正确的重叠部分应该是从S1起始位置直到结尾，故S1尾部减去起始位置应该等于重叠串长度 if(s1.length() - i == len && len > max) max = len, index = i;//Index标记重叠串在S1中的起始位置 }if(index == -1) return s1 + s2;//无重叠部分，直接叠加 else return s1.replace(index, max, s2);//将重叠部分替换为S2，如GATTA + TACA -> GATTACA, 重叠部分为TA
}
void DFS(string s, int now)//暴力深搜，对所有字符串全排列，当两个字符串“首尾相接”时合并重叠部分，一直合并到最后即是答案
{
if(now == n)// {
if(s.length() < min_len)//递归结束，更新最小值 min_len = s.length();return ;}REP(i, 0, n)if(book[i] == 0){
book[i] = 1;DFS(merge(s, v[i]), now + 1);//将合并后的字符串传入下一层DFS book[i] = 0;}
}
int main()
{
string empty;//空字符串的作用是启动DFS while(cin >> n){
min_len = 999;//重置最小值 REP(i, 0, n) cin >> v[i];DFS(empty, 0);cout << min_len << endl;}return 0;
}