Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task: Word Chains
发信站: 哈工大紫丁香 (2002年03月29日13:52:55 星期五), 站内信件

Task: Word Chains
A word consists of at least one and at most 75 lowercase letters (from `a' t
o `z'). A list of one or more words is called a chain when each word in that
 list, except the first, is obtained from the preceding word by appending on
e or more letters on the right. For instance, the list
i
in
int
integer
is a chain of four words, but the list
input
integer
is not a chain. Note that every list of one word is a chain.
Input Data
Your program is given a list of words in the file INPUT.TXT. This list conta
ins at least one word and all of the words together have no more than 2,000,
000 letters. The input is terminated with a line containing a single period 
(`.'). All other lines contain one word each. The list is sorted lexicograph
ically using the standard alphabetical ordering (as in an English dictionary
). There are no duplicate words in the list.
Output Data
The length of a chain is the number of words it contains. Your program shoul
d write to file OUTPUT.TXT a longest chain of words taken from the input. Ea
ch word should be on a separate line.
If there is more than one chain of maximum length, your program should outpu
t only one of these chains. It does not matter which one.
Example Input and Output
Figure 1 gives an input file with seven words and the corresponding output f
ile. The input contains one chain of length four and no chains with more tha
n four words.
____________    _____________
|INPUT.TXT |    |OUTPUT.TXT |
|__________|    |___________|
|i         |    |i          |
|if        |    |in         |
|in        |    |int        |
|input     |    |integer    |
|int       |    |___________|
|integer   |
|output    |
|.         |
|__________|
Figure 1: Example input and output


--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]