题目描述

Adrian 很喜欢诗歌中的韵。他认为，两个单词押韵当且仅当它们的最长公共 后缀的长度至少是其中较长单词的长度减一。也就是说，单词 A 与单词 B 押韵 当且仅当 LCS(A, B) ≥ max(|A|, |B|) – 1。（其中 LCS 是最长公共后缀 longest common suffix 的缩写）
现在，Adrian 得到了 N 个单词。他想从中选出尽可能多的单词，要求它们能 组成一个单词序列，使得单词序列中任何两个相邻单词是押韵的。

输入

第一行是一个整数N。
接下来N行，每行一个由小写英文字母组成的字符串，表示每个单词。所有单词互不相同。

输出

输出一行，为一个整数，表示最长单词序列的长度。

题解

首先看到LCS可以考虑对字符串逆序建立Trie树，关键在于怎么对于这棵树怎么处理出最长链。
首先我们知道设树上某个节点x作为根节点，对于这个节点构造出的最大单词序列的解ans，应该为
设以x为根的最长链为f[x]，次长链为g[x],以x为根的孩子节点为son[x]
则ans = f[x] + g[x] + son[x] + word_end[x] – 2
从字符串结束位置进行树形dp即可

代码

C/C++

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

using namespace std;
const int maxn = 3e6 + 1e2;

int sum, f[maxn], g[maxn];
int head[maxn], pcnt = 1, ecnt;
struct Node {
    int num, next;
} edges[maxn];

void addEdge(int s, int e) {
    edges[++ecnt].num = e;
    edges[ecnt].next = head[s];
    head[s] = ecnt;
}

int fa[maxn], sons[maxn], val[maxn];
bool word_end[maxn];
string s;

void trie(const string::reverse_iterator &b, string::reverse_iterator e) {
    int root = 1;
    auto iter = b;
    for (; iter != e; ++iter) {
        bool flag = true;
        auto w = *iter - 'a' + 1;
        for (int i = head[root]; i && flag; i = edges[i].next) {
            if (val[edges[i].num] == w) {
                root = edges[i].num;
                flag = false;
            }
        }
        if (flag) break;
    }
    for (; iter != e; ++iter) {
        f[pcnt] = g[pcnt] = 1;
        val[++pcnt] = *iter - 'a' + 1;
        addEdge(root, pcnt);
        fa[pcnt] = root;
        root = pcnt;
    }
    word_end[root] = true;
    sons[fa[root]]++;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        trie(s.rbegin(), s.rend());
    }
    for (int i = pcnt; i; --i)
        if (word_end[i]) {
            if (f[fa[i]] < f[i] + sons[i]) {
                g[fa[i]] = f[fa[i]];
                f[fa[i]] = f[i] + sons[i];
            } else g[fa[i]] = max(g[fa[i]], f[i] + sons[i]);
        }
    for (int i = pcnt; i; --i) {
        sum = max(sum, f[i] + g[i] + sons[i] + word_end[i] - 2);
    }
    cout << sum << "\n";
}