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

· · 题解

考虑翻转每一个字符串，这样公共后缀就变成了公共前缀。

公共前缀？建出字典树来。

（点权代表这个点有没有单词结尾）

那么，两个单词押韵，当且仅当它们的尾部节点在字典树上有父子或兄弟关系。

也就是说，序列中每一个单词的下一个单词可以是它的任意一个非空兄弟、非空父亲或非空儿子上。

一颗子树上，能遍历到最多点的情况应该长成下面这个样子：

但注意，这种情况无法对更大的子树做出贡献，因为一旦下去就再也上不来了。

所以，不仅要记录能遍历到最多点（即深入两根枝条）的情况，也要记录只深入了一根枝条的最多点数。

还有，根节点也可能没有对应的单词。

所以，设 dp(u,1\ or\ 0,1\ or\ 2) 表示在以 u 为根的子树中，选/不选根，深入了1\ or\ 2 根枝条的最大单词数。

设 s 为 u 的非空儿子数，son(u) 表示 u 的非空儿子集合

当 s \geqslant 1 时，

dp(u,0,1)=\max_{v\in son(u)} dp(v,1,1)+s-1

当 s \geqslant 2 时，

dp(u,0,2)=\max_{v\in son(u),w \in son(u),v \ne w} dp(v,1,1)+dp(w,1,1)+s-2

上面的一遍深搜 O(\sum|S|) 处理即可。

若 u 非空，则 dp(u,1,1)=dp(u,0,1)+1,\ dp(u,1,2)=dp(u,0,2)+1

答案可能是任意 u 的 dp(u,0\ or\ 1,1\ or\ 2),取最大值即可。

代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 3e6 + 10;
int m,to[N][30],val[N],n,siz[N][2][3];
void Insert(string s)
{
    int id = 0;
    for(char c : s)
    {
        if(to[id][c - 'a' + 1]) id = to[id][c - 'a' + 1];
        else
        {
            n++;
            to[id][c - 'a' + 1] = n;
            id = n;
        }
    }
    val[id]++;
}
void dfs(int u)
{
//  cout << u << endl;
    int maxx = -1,maxxx = -1,s = 0;
    for(int i = 1; i <= 26; i++)
    {
        if(to[u][i])
        {
            dfs(to[u][i]);
            if(val[to[u][i]])
            {
                s++;
                if(siz[to[u][i]][1][1] > maxx) maxxx = maxx, maxx = siz[to[u][i]][1][1];
                else if(siz[to[u][i]][1][1] > maxxx) maxxx = siz[to[u][i]][1][1];

            }
        }
    }
    if(maxxx != -1) siz[u][0][2] += maxx + maxxx;
    if(maxx != -1) siz[u][0][1] += maxx;
    if(s >= 1) siz[u][0][1] += s - 1;
    if(s >= 2) siz[u][0][2] += s - 2;
    if(val[u]) siz[u][1][2] = siz[u][0][2] + 1, siz[u][1][1] = siz[u][0][1] + 1;
}
int main()
{
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        string s; cin >> s;
        reverse(s.begin(),s.end());
        Insert(s);
    }
    dfs(0);
    int ans = -1;
    for(int i = 0; i <= n; i++) ans = max(ans,max(siz[i][0][2],siz[i][1][2]));
    for(int i = 0; i <= n; i++) ans = max(ans,max(siz[i][0][1],siz[i][1][1]));
    cout << ans << endl;
    return 0;
}
//ctj可耻！