题目描述

小木木和小凳子是两个聪明的孩子，他们五岁的时候就开始学习英语了。

英语老师教他们玩一个很简单的游戏。

老师给他们一张全小写并无特殊符号的英语单词表，单词表如下：

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc
然后让他们从单词表里找词语接龙。

接龙的规则如下:

前一个单词拥有的所有字母，在后一个单词里必须出现，而且字母出现次数不少于前一单词。
后一个单词的长度比前一个单词的长度恰好多 1。
对于以上例子，一合法的接龙为:

ab
bar
crab
cobra
carbon
carbons
他们之中，谁接龙的长度长，谁就赢了。

小木木肯定不想输，所以找到你来帮忙。

样例

输入样例：
ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc
输出样例：
6
ab
bar
crab
cobra
carbon
carbons

算法1

(哈希 + dfs) $O(n^2)$

先对字符串的各字母出现次数哈希，然后再尝试分别给各个字符串增加一个字母，看是否存在这样的字符串，有的话，那么可以连一条边，最后dfs求出DAG图最长路即可。

时间复杂度o(n)

C++ 代码

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

using namespace std;

const int N = 1e4 + 10 , M = 2e6 + 10 , P = 131;

typedef unsigned long long ULL;

int n , cnt[N][27];
ULL p[N];
bool st[N];
int h[N], e[M], ne[M], idx;
unordered_map<ULL , int> H;
int ans = 0;
string s[N];
vector<string> path,curpath;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}


ULL get_hash(int c[]){

    ULL res = 0;
    for(int i = 0 ; i < 26 ; i++)
    {
        res = res * P + c[i];
    }

    return res;
}

void dfs(int u,int res){

    st[u] = true;

    curpath.push_back(s[u]);
    if(ans < res)
    {
        path = curpath;
        ans = res;
    }
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int ver = e[i];
        if(!st[ver])
           dfs(ver , res + 1);
    }
    curpath.pop_back();
    st[u] = false;
}

int main(){

    while(cin >> s[++n]);
    n--;
    p[0 ]=1;
    for(int i = 1 ; i <= 27 ; i++)
       p[i] = p[i - 1] * P;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j < s[i].size() ; j++)
            cnt[i][s[i][j] - 'a']++;
        H[get_hash(cnt[i])] = i;
    }           

    memset(h, -1, sizeof h);
    for(int i = 1 ; i <= n ;i++)
    {
        for(int j = 0 ; j < 26 ; j++)
        {
            ++cnt[i][j];
            ULL ver = get_hash(cnt[i]);
            if(H[ver])
            {
                add(i , H[ver]);
                //cout << i << "  " << ver << endl;   
            }
            --cnt[i][j];    
        }
    }

    for(int i = 1 ; i <= n ; i++)
    {
        memset(st, 0, sizeof st);
        curpath.clear();
      //  cout << s[i] << endl;
        dfs(i, 1);
    }

    cout << ans << endl;
    for(auto x : path)
       cout << x << endl;
    return 0;
}