洛谷P1019 单词接龙题解（超详细注释）

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;
}