代码解释

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N =21;
int n;
string word[N];
int g[N][N];
int used[N];
int ans;

void dfs(string dragon,int last)
{
    ans=max((int)dragon.size(),ans);  //找寻最长的单词，通过dragon这个单词来进行更新
    used[last]++;   //这个单词用的次数
    for(int i=0;i<n;i++)
      if(g[last][i]&&used[i]<2)         //如果这个单词的次数小于2 and  上一个单词和第i个单词的重复数量不为零
      dfs(dragon+word[i].substr(g[last][i]) , i );   
      //搜索dragon+word[i]这个单词从g[last][i]这个重复的地方开始，并标记这个序号
     //不要为什么没有更新last这个单词的使用次数，因为在场面已经更新了
    used[last]--;  //恢复现场
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)  cin>>word[i];   //按照字符串进行输入，防止空格的读入
    char start;
    cin>>start;//龙的开头字母


    //预处理   处理单词与单词之间是否存在重复的子序列
    for(int i=0;i<n;i++)
       for(int j=0;j<n;j++)
       {
           string a=word[i],b=word[j];    //两个字符串
           for(int k=1;k<min(a.size(),b.size());k++)
             if(a.substr(a.size()-k,k)==b.substr(0,k))    //字符串函数  a的后k个字母和b的前k个字母
             {
                 g[i][j]=k;        //标记长度   //单词与单词之间重复的最短长度
                 break;
             }
       }

    for(int i=0;i<n;i++)
      if(word[i][0]==start)  //寻找哪个字符串可以和start向匹配
      dfs(word[i],i);       //从这个单词开始搜,并标记这个单词的序号

    cout<<ans<<endl;
    return 0;
}