题解 P5755 【[NOI2000]单词查找树】

· · 题解

Description

P5755

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：

  • 根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
  • 从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
  • 在满足上述条件下，该单词查找树的节点数最少。

例：图一的单词列表对应图二的单词查找树

对一个确定的单词列表，请统计对应的单词查找树的节点数 （包括根节点）

Solution

其实我们计算整个树的节点数运用读入的字符串的长度差就可以解决了。

读入的时候运用一个字符串数组存储即可。

然后读入之后要用一个 sort 进行排序。（然后才好计算差值）

然后前后两个字符串的差定义为第二个字符串的长度减去两个字符串的公共部分的长度。

最后把这些差相加即可。

记得最后加个 1 啊（因为这个 WA 了 /kk）因为还要 包括根节点。

Code

#include <bits/stdc++.h>

using namespace std;

string s[10086];

int main () {
    int len = 0;
    while (cin >> s[++len])
        continue;
    sort(s + 1, s + len + 1);
    int length = 0;
    for (int i = 1; i <= len; i++) {
        if (i == 1) {
            length += s[i].length();
            continue;
        }
        int tmp = 0;
        while (s[i][tmp] == s[i - 1][tmp] && tmp < s[i - 1].length())
            tmp++;
        length += s[i].length() - tmp;
    }
    printf("%d", ++length);
    return 0;
}

最后在 while (s[i][tmp] == s[i - 1][tmp] && tmp < s[i - 1].length()) 这一大行说明一下意思：

By Shuchong
2020.7.7