感觉这题的关键在于dfs函数的参数，要提前确定自己需要用到什么

#include <iostream>
#include <cstring>

using namespace std;

const int N=22;
string word[N];

//gij表示第i个单词后缀和第j个单词前缀有多少相同
int g[N][N];
int st[N];
int res=0;
int n;

// dk为当前拼接字符串的长度，last为上一个字符串（在判断g时起作用）
void dfs(string dk,int last)
{
    res=max(res,(int)dk.size());
    //last 这个位置的字符串使用的次数+1
    st[last]++;
    for(int i=1;i<=n;i++)
    {
        if(g[last][i]!=0 && st[i]<2)
        {
            dfs(dk+word[i].substr(g[last][i]),i);
        }
    }
    st[last]--;

}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>word[i];
    }
    char start;
    cin>>start;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            string a=word[i];
            string b=word[j];
            //k枚举长度
            for(int k=1;k<min(a.size(),b.size());k++)
            {
                if(a.substr(a.size()-k,k)==b.substr(0,k))
                {
                    g[i][j]=k;
                    //因为我们希望越小的重叠部分越好，所以找到第一个重叠部分时就break
                    break;
                }
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(word[i][0]==start)
        {
            dfs(word[i],i);
        }
    }
    cout<<res;

    return 0;
}

二刷，没什么压力，记得last代表的含义，g[i][j]的含义即可

g[i][j]：以i单词在前，j单词在后的最小公共部分

#include <iostream>
#include <cstring>

using namespace std;

const int N=22;
string words[N];
int st[N];
int g[N][N];
int res;
int n;

//last记录最后接上的单词的序号
int dfs(string dk, int last)
{
    res=max(res,(int)dk.size());


    for(int i=1;i<=n;i++)
    {
        st[last]++;
        if(g[last][i]!=0&&st[i]<2)
        {
            dfs(dk+words[i].substr(g[last][i]),i);
        }
        st[last]--;
    }

}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>words[i];
    }
    char start;
    cin>>start;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            string a=words[i];
            string b=words[j];
            //k枚举长度
            for(int k=1;k<min(a.size(),b.size());k++)
            {
                if(a.substr(a.size()-k,k)==b.substr(0,k))
                {
                    g[i][j]=k;
                    break;
                }
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(words[i][0]==start)
        {
            dfs(words[i],i);
        }
    }
    cout<<res;


    return 0;
}

2023/12/2

第一遍没有思路，看了视频会了
总体思路：暴搜每个以start开头的单词，遍历它后面可以接的所有的情况；接上下一个单词后，紧接着遍历该单词后面可以接的单词。

因此要初始化一个数组，存储当前字符串后面可以接的字符串的公共长度 k。在计算总串时，总串 = 总串 + 要接的字符串从k开始到末尾的子串

#include <iostream>
#include <cstring>

using namespace std;

const int N=30;
string word[N];
int n;
char start;
// gij: 以第i个字符串开头，第j个字符串结尾，中间公共部分的长度
int g[N][N];
int st[N];
int res;

void dfs(string dg, int last)
{
    res = max((int)dg.size(), res);

    // last字符串的使用次数+1
    st[last] ++;
    // 遍历所有可以接在第last个字符串后面的字符串
    for(int i=1;i<=n;i++)
    {
        if(g[last][i]!=0 && st[i]<2)
        {
            dfs(dg + word[i].substr(g[last][i]), i);
        }
    }
    st[last] --;

}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>word[i];
    }
    cin>>start;

    // string qq = "asdfg";
    // cout<<qq.substr(0,2)<<endl;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            string a = word[i];
            string 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))
                {
                    g[i][j] = k;
                    break;
                }
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(word[i][0] == start)
        {
            dfs(word[i], i);
        }
    }

    cout<<res;
    return 0;

}