题目描述

通过字符串拼接，找出最长的拼接串，每个串最多用两次，重叠部分只计算一次。

分析

通过找路径，找出一种拼接。 $n\le15$ 可以随便乱搞。 可以提前处理出点间的连通关系，简单 $n^2$ 两两判断即可。这里考虑一个 $STL$ 库的函数 $substr$ 用来截取字符串的子串来判断 $i$ 号点与 $j$ 号点是否存在联通关系建边。不会用自己上网
将每个串长度转化为点权，重叠部分转化为边权，直接暴力深搜，每次打标记加回溯，路径长度便是每个点权减边权。来一个 $ans$ 统计最大值。

聪明的小朋友到这里就可以退出题解去愉快的AC本题。

#include<bits/stdc++.h>
using namespace std;
string s[20];
int ans=0;
struct 
{
	int v,next,w;
}edge[400];
int head[20];
int w[20];
int cnt=0;
void add(int u,int v,int w)
{
	edge[++cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
int vis[20];
void dfs(int u,int len)
{
	len+=w[u];
	ans=max(ans,len);
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].v;
		if(vis[v]<2)
		{
			vis[v]++;
			dfs(v,len-edge[i].w);
			vis[v]--;
		}
	}
}
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		w[i]=s[i].size();
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int len1=s[i].size(),len2=s[j].size();
			for(int k=min(3,min(len1,len2));k>=1;k--)//题目要求最长为3
			{
				if(s[i].substr(len1-k,k)==s[j].substr(0,k))
				{
					add(i,j,k);
					break;//题目要求最大重叠，所以从大到小，找到直接退出
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		vis[i]=1;
		dfs(i,0);
		vis[i]=0;
	}
	cout<<ans;
}

建边$O(n^2)$ 搜索最坏为$O(n^4)$