NOI '00 P4 - Trie

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 16M

Problem types
National Olympiad in Informatics, China, 2000

When performing grammar analyses, it is commonly needed to check whether a word is present in our word list. To improve the speed of the search, it is common to draw out the corresponding trie for the word list, which is characterized as follows:

  • The root node does not contain letters, but every other node other than the root each contains a single uppercase English letter.
  • For a path from the root to any node, the letters on that path are joined together to form a letter sequence which is the corresponding word of that node. Each word from the word list has a corresponding node on the trie.
  • Under the above conditions, the number of nodes in the trie must be as few as possible.

Ex. The following is a word list and its corresponding trie.

A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

Given a particular word list, please find the number of nodes in the corresponding trie (including the root).

Input Specification

The input contains a word list, with one word per line. Each word will consist of only uppercase letters, and will not exceed 63 characters in length. The total length of the input will not exceed 32K, and there will be at least one line of data.

Output Specification

The output should contain one integer, the number of nodes in the trie constructed from the given word list.

Sample Input

A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

Sample Output

13

Problem translated to English by Alex.


Comments

There are no comments at the moment.