这题有很多人说是字典树，我更愿意把它放在我最开始也是想用字典树做的，但是题目中一句话（Any two parts of the sentence cannot intersect.）说各个部分不交叉，名词，代词就是主语宾语，动词就是谓语。这提醒我这题可能没有那么麻烦。事实证明，用字典树有点杀鸡用牛刀了。
把词性数字化0-8；按照要求建立词性邻接矩阵。如果2个词性可以相邻，矩阵值为1，否则为0。字典中单词按字典序排序。
输入句子后，单词分割并小写化。把单词按词性转化成数字。看当前单词与上一个单词词性是否邻接即可，注意介词短语单独分析。分类代码中注释很详细。
注意几点：
1.句子中，不是字母的都是无用字符。
2.介词短语中，名词不可以用形容词修饰。
3.谓语动词唯一
4.抛弃已有的语法观点，坚持题目要求。
5 句子最后一个词必须是不及物动词或者名词。
6句子开头必须是介词或者名词或者代词或者冠词。
7介词短语是单独分析的

0-7对应题中给出的词性的顺序。8是V.
以下是邻接矩阵
    g[9][9]={0,0,0,1,1,0,1,1,1,
             0,0,0,1,1,0,1,1,1,
             1,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,1,1,1,
             0,1,0,0,0,1,0,0,0,
             1,0,1,0,0,0,0,0,0,
             0,1,0,0,1,1,0,0,0,
             0,0,0,0,1,0,0,0,0,
             0,1,0,0,1,1,0,0,0
            };
详细代码：
http://hi.baidu.com/%E5%B0%91%E4%B8%80%E6%96%A4/blog/item/ec4b7819040009be4aedbcbd.html

• Re:字典树，杀鸡焉用牛刀！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ (33) xuhaoran510 2010-05-07 18:08:22