本文最后更新于 2120 天前,其中的信息可能已经有所发展或是发生改变。
内容纲要
题目描述
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";
}