洛谷 P7537 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-22 17:24:32

发布于：北京

7阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 个字符串
规定两个字符串 $A$ 和 $B$ 的最长公共后缀长度为 $LCS(A,B)$
规定两个字符串 $A$ 和 $B$ 当 $LCS(A,B) \ge$ 两字符串较长长度 $-1$ ，则称 $A$ 和 $B$ 是押韵的
允许：
求最长押韵子序列（只需要保证相邻两项押韵即可）

限制：

1.3 题目数据范围与猜测

$1 \le n \le 5\times10^5 \longrightarrow O(n)$

1.4 一句话概括题意

有一些字符串，求最长押韵子序列

2 题目破题推导

2.1 规律分析

首先，押韵只有可能有两种情况

两字符串长度相等，首位不相等
两字符串长度相差 $1$ ，较短字符串是较长字符串前缀

2.2 正向思维转逆向思维

因为这题要求后缀，但后缀操作起来比较麻烦，因此考虑转成前缀操作
可以理解成：
押韵变成前缀之后只有可能有两种情况

两字符串长度相等，末尾不相等
两字符串长度相差 $1$ ，较短字符串是较长字符串后缀

2.3 题意转化

（现在必须结合着字典树来说）
当我们倒着插入进字典树后，押韵的字符串有两种情况：相邻两个末尾是父子关系或者是亲兄弟关系
因此相当于在字典树上选若干个单词终点，相邻两个选出单词必须是父子/亲兄弟关系，求最多单词数量

2.4 继续找规律

因为我们不仅选出的字符串序列可能是这样：

---------
--------
----
----
-

还可以往另外一段延伸（也就是加入了波峰和波谷）

---------
--------
----
----
-
---
---
----
--------
-----------

2.5 计算方案

那波谷前面的那一部分有多少呢？
就是 $u$ 子树中最大的子序列长度外加子树内的所有单词结尾数量
那这整个有多少呢？
首先因为可以往两端扩展，因此相当于：

$u$ 子树中最大的两个子序列长度
除了这两个子树以外的单词结尾子树数量
再加（本身是否为单词结尾），就算这一项不是单词结尾，也可以作为另外两个是单词结尾的孩子节点的过渡

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：字典树 $\longrightarrow$ $\huge{字典树}$
关键词：树上问题，动态求取最大值 $\longrightarrow$ $\huge{树形dp}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 3e6 + 10, M = 26;
int trie[N][M];   
int ed[N];
int idx;
int get(char c){
	return c - 'a';
}
void insert(string s){
	int now = 0;
	int len = s.size();
	for (int i = 0;i < len;i++){
		int ch = get(s[i]);
		if (trie[now][ch] == 0){
			trie[now][ch] = ++idx;
		}
		now = trie[now][ch];
	}
	ed[now]++;
}
int dp[N], ans;
void dfs(int u){
    int v;
    int siz = 0, mx1 = 0, mx2 = 0;
    for (int i = 0;i < 26;i++){
        v = trie[u][i];
        if (v){
            dfs(v);
            siz += ed[v];
            if (mx1 < dp[v]){
                mx2 = mx1;
                mx1 = dp[v];
            } else if (mx2 < dp[v]){
                mx2 = dp[v];
            }
        }
    }
    if (ed[u]){
        dp[u] = mx1 + max(siz, 1);
    }
    ans = max(ans, mx1 + mx2 + ed[u] + max(siz - 2, 0));
}

int main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        insert(s);
    }
    dfs(0);
    cout << ans;
    
    return 0;
}