Luogu P7537 [COCI2016-2017#4] Rima 题解

题意

简单类说就是通过拼接字符串，实现两个字符串之间的最长公共后缀长度恰好是较长的字符串的长度 \(-1\)。并使得最长公共后缀长度最长。

思路

随便做即可。

首先我们观察到题目要求的是后缀，但是显然求后缀的算法并不是很多，于是我们考虑将其反转。然后题目就变成了求前缀。

反转完我们继续考虑怎么做，对于这种字符串的问题，我们果断猜测使用 Trie 树，或者说字典树。我们先将所有的字符串一起扔到一个字典树里面。

经过了一番的思考，我们发现在树上进行一次 DP 可以完成答案的统计。

于是我们从根据根节点开始往下 DFS 遍历整个 Trie 树。定义状态 \(f_i\)，我们每一次转移之前先获得子节点中 \(f\) 值的最大值和次大值，用来统计答案。同时我们还要统计有多少字符串在子节点中截止。

当我们此时的状态是一个有字符串终结的状态时，我们才进行 \(f_i\) 的转移，方程为 \(f_i = maxn + \max(cnt,\, 1)\)。其中 \(maxn\) 是子节点中最大的 \(f\) 值，\(cnt\) 是子节点中截止的字符串的个数。

然后我们考虑如何统计答案。容易发现，对于每一个状态，其答案是 \(maxn + smaxn + e_u + \max(0,\, cnt - 2)\) 其中 \(e_u\) 表示在状态 \(u\) 终结的字符串数量，\(smaxn\) 为次大值，其余同上。

代码

#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

string str[500009];
int n, nxt[1000009][30], cnt, e[1000009], f[1000009], ans;

void dfs(int u, int dep) {
    int cnt = 0, maxn = 0, smaxn = 0;
    for (int i = 0; i < 26; i++) {
        if (nxt[u][i]) {
            cnt += e[nxt[u][i]];
            dfs(nxt[u][i], dep + 1);
            if (maxn < f[nxt[u][i]]) {
                smaxn = maxn;
                maxn = f[nxt[u][i]];
            } else if (smaxn < f[nxt[u][i]]) {
                smaxn = f[nxt[u][i]];
            }
        }
    }
    if (e[u]) {
        f[u] = maxn + max(cnt, 1LL);
    }
    ans = max(ans, maxn + smaxn + e[u] + max(0LL, cnt - 2));
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> str[i];
        reverse(str[i].begin(), str[i].end());
        int p = 0;
        for (char j: str[i]) {
            if (!nxt[p][j - 'a']) {
                nxt[p][j - 'a'] = ++cnt;
            }
            p = nxt[p][j - 'a'];
        }
        e[p] += 1;
    }
    dfs(0, 0);
    cout << ans;
}