RQNOJ PID322——单词查找树

题目描述
在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都要画出与单词列表所对应的单词查找树,其特点如下:
l 根节点不包含字母,除根节点外每一个节点都仅包含一个大写英文字母;
l 从根节点到某一节点,路径上经过的字母依次连起来所构成的字母序列,称为该节点对应的单词。单词列表中的每个词,都是该单词查找树某个节点所对应的单词;
l 在满足上述条件下,该单词查找树的节点数最少。

对一个确定的单词列表,请统计对应的单词查找树的节点数(包括根节点)
输入格式
一个单词列表,每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成,长度不超过63个字符。文件总长度不超过32K,至少有一行数据。
输出格式
仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。
样例输入
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

样例输出
13


其实,可以发现单词的长度,就是根到结点的距离
那么我们要避免不必要的重复,那么我们就要保证前面的单词都是有序的。So,就排吧
那么,这次要插入的字母数,就是每一位上不相同的字母个数。(这个处理很容易,一个while就行了)
最后记得+1,(其实,我也不知道为什么)


代码如下:

var  n,i,j,ans:longint;
     a:array[0..10000]of string;
begin
  while not eoln() do
    begin
      inc(n);
      readln(a[n]);
    end;
  for i:=1 to n-1 do
    for j:=i+1 to n do
      if a[i]>a[j] then
        begin
          a[0]:=a[i];
          a[i]:=a[j];
          a[j]:=a[0];
        end;
  ans:=length(a[1]);
  for i:=2 to n do
    begin
      j:=1;
      while (a[i,j]=a[i-1,j])and(j<=length(a[i-1])) do inc(j);
      ans:=ans+length(a[i])-j+1;
    end;
  writeln(ans+1);
end.
原文地址:https://www.cnblogs.com/Comfortable/p/8412287.html