https://www.luogu.org/problem/P1019
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char s[50][15];
int check(int x,int y)
{
for(int i=strlen(s[x])-1;i>=0;i--)//从后往前比，这样能够找到最小的重合
{
int j=i;
int k=0;//第一个单词x从i往最后比，第二个单词从头开始比
while(s[x][j]==s[y][k]&&j<strlen(s[x])&&k<strlen(s[y]))//如果两个单词的对应位置相同并且都没有出去（过了最大的长度）
{
j++;
k++;//那么都到下一位
}
if(j==strlen(s[x]))return strlen(s[x])-i;//如果出来的时候第一个单词已经比完了，就说明可以匹配上了，返回重合的长度
}
return 0;
}
int n;
int vis[30];
int ans;
int f[105][105];
void dfs(int len,int wz)
{
for(int i=1;i<=n;i++)
{
int tmp=f[wz][i];//再次把两个单词之间的连接长度取出
if(vis[i]!=2&&tmp)/如果用了没过两次还能连，就连上试试
{
vis[i]++;//用了一次
dfs(len+strlen(s[i])-tmp,i);//长度变成了新连接上的单词的长度减去两个单词重合的长度，龙的最后一个单词变成了i
vis[i]--;//恢复现场
}
}
ans=max(ans,len);//每次都要更新
}
void init()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int tmp=check(i,j);//检查两个单词的重合程度
if(tmp&&tmp!=strlen(s[i])&&tmp!=strlen(s[j]))//如果两个单词有重合并且不是一个完全包括了另外一个
{
f[i][j]=tmp;//那么就可以记录下来了
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
}
init();//预处理，将每两个单词之间能不能接，如果能接，接了多长记录下来
char head;
cin>>head;//读入龙头
for(int i=1;i<=n;i++)
{
if(s[i][0]==head)//如果有一个单词可以接到脖子位置
{
vis[i]++;//那么这个单词首先被用了一次
dfs(strlen(s[i]),i);//从脖子长度（包含了头），脖子在零件库s中的位置开始
vis[i]--;//别忘了这里的返回现场也不能疏忽
}
}
printf("%d\n",ans);
return 0;
}