洛谷题单指南-字符串-P1481 魔族密码

原题链接：https://www.luogu.com.cn/problem/P1481

题意解读：在n个字符串中找到最长的词链长度，定义字符串a、b、c可以形成词链，即a是b的前缀、b是c的前缀。

解题思路：

1、Trie树定义

Trie树，也称前缀树、字典树，核心思想是将字符串拆解为单个字符，每个字符是树的一条边，节点是字符添加到树中的顺序编号，这样可以避免冗余存储，同时也可以快速查找一个字符串或者前缀是否存在。

如i,int,integer,intern,internet构成的Trie树为：

根节点是0，蓝色节点是字符串的中间字符，绿色节点表示此节点是一个字符串的结尾（绿色节点到根节点之间是一个完整字符串）。

0到1表示i，0到3表示int，0到7表示integer，0到9表示intern，0到11表示internet。

在建立Trie树的时候，会提取字符串的每一个字符，从根节点开始看这个字符是否已经有边了，如果没有就建一条边，如果有就沿着已有的边往下一层继续看下一个字符。

2、Trie树实现

普通的树可以用一维数组记录节点之间的父子关系，而Trie树要记录字符和节点，可以通过二维数组来实现Trie树

定义int son[N][26], idx, cnt[N]

idx用来表示节点的编号，son[u][v] = idx表示u节点到idx节点之间是字符v（0~25分别对应a~z）

Trie树有三个核心操作：添加字符串、查找字符串是否存在，查找前缀是否存在

添加一个字符串到Trie树：

void add(string str)
{
    int u = 0; //从根节点开始
    for(int i = 0; i < str.size(); i++) //遍历每一个字符
    {
        int v = str[i] - 'a';
        if(son[u][v] == 0) son[u][v] = ++idx; //如果从u没有一条字符是v的边，则建立一条，u指向++idx
        u = son[u][v]; //把u往下移动一层
    }
    cnt[u]++; //统计以u结尾字符串数量
}

查询一个字符串是否存在：

bool find(string str)
{
    int u = 0, res = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int v = str[i] - 'a';
        if(son[u][v] == 0) return false;
        u = son[u][v];
    }
    return cnt[u] > 0;
}

查询一个字符串前缀是否存在：

bool find(string str)
{
    int u = 0, res = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int v = str[i] - 'a';
        if(son[u][v] == 0) return false;
        u = son[u][v];
    }
    return true;
}

3、核心逻辑

对于此题，只需要将所有字符串都存入Trie树，然后查找每一个字符串，查找的过程中累加路径中出现的单词数量，更新最大值即可。

100分代码：

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

const int N = 2000 * 75 + 5;
int n;
string str[N];
int son[N][26], idx, cnt[N];
int ans;

void add(string str)
{
    int u = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int v = str[i] - 'a';
        if(son[u][v] == 0) son[u][v] = ++idx;
        u = son[u][v];
    }
    cnt[u]++;
}

bool find(string str)
{
    int u = 0, res = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int v = str[i] - 'a';
        if(son[u][v] == 0) return false;
        u = son[u][v];
        res += cnt[u];
    }
    ans = max(ans, res);
    return true;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> str[i];
        add(str[i]);
    } 
    for(int i = 1; i <= n; i++) find(str[i]);
    cout << ans;
    return 0;
}