作者:
67ovo
,
2022-08-05 09:11:47
,
所有人可见
,
阅读 3
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=25;
int n;
string s[N];
int rel[N][N];
int used[N];
int ans;
void deal()
{
for(int i=0;i<n;i++)//预处理所有能接到一起的单词
{
for(int j=0;j<n;j++)
{
//注意,两个单词可以拼到一起,并不一定是重合
for(int k=1;k<(int)min(s[i].size(),s[j].size());k++)
{
if(s[i].substr(s[i].size()-k,k)==s[j].substr(0,k))
{
rel[i][j]=k;
break;//因为要最长的串,所以找最短的重合部分就行
}
}
}
}
}
void dfs(string dragon,int current)//当前拼成的字符串,当前用到的最后一个字符串
{
ans=max(ans,(int)dragon.size());//max比较,两个参数必须是同类型的
used[current]++;
for(int i=0;i<n;i++)
{
if(used[i]<2&&rel[current][i])
{
dfs(dragon+s[i].substr(rel[current][i]),i);
}
}
used[current]--;
}
int main()
{
cin>>n;
char start;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
cin>>start;
deal();
for(int i=0;i<n;i++)
{
if(s[i][0]==start)
{
dfs(s[i],i);
}
}
cout<<ans<<endl;
return 0;
}