python/TangDou/AcWing/SearchOrder/1117.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
string word[N];
int cnt[N];
int res;

int getSameLength(string a, string b) {
    for (int i = 1; i < min(a.size(), b.size()); i++)
        if (a.substr(a.size() - i, i) == b.substr(0, i))
            return i;
    return 0;
}

void dfs(int u, string str) {
    res = max((int)str.size(), res); // 不断刷新龙的长度

    // 记录该字符串使用次数
    for (int i = 0; i < n; i++) { // 遍历所有字符串，找出可以接在u后面串
        int len = getSameLength(word[u], word[i]);
        // 最小公共长度（可以保证龙最长），并且，使用次数小于2次
        // 最小公共长度对于后面的串而言，也是前缀位置
        if (len && cnt[i] < 2) {
            cnt[i]++;
            dfs(i, str + word[i].substr(len));
            cnt[i]--;
        }
    }
}

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

    char st;
    cin >> st;

    for (int i = 0; i < n; i++) // 枚举每个字符串
        // 如果该字符串的首字母是指定的起点字母st
        if (word[i][0] == st) {
            cnt[i]++;
            dfs(i, word[i]); // 开始将当前搜索到的字符串作为首串开始深搜
            cnt[i]--;
        }

    cout << res << endl; // 最大长度
    return 0;
}