题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<unordered_map>
#include<string>
using namespace std;

const int N = 20;
string word[N];
int g[N][N];
int used[N];
int n;
int res;

void dfs(string dragon, int last)
{
    res = max(res, (int)dragon.size());
    used[last] ++;

    for (int i = 0; i < n; i ++)
    {
        if (!g[last][i]) continue;
        if (used[i] == 2) continue;
        int k = g[last][i];
        dfs(dragon + word[i].substr(k), i);
    }

    used[last] --;

}

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

    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) == b.substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
        }

    for (int i = 0; i < n; i ++)
        if (word[i][0] == c)
            dfs(word[i], i);

    cout << res;
    return 0;

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla