Ignatius最近遇到一个难题,老师交给他很哆单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). 

输入数据的苐一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 

注意:本题只有一组测试数据,处理到文件结束. 

对于每个提问,给出以该字符串为前缀的单词的数量.  

0

這道题是我的一个学长讲给我们的我觉得题目比较有代表意义，并且用到的方法也很好所以就写这篇博客，再分析一下本题用到的主要方法是字典树，相信网上有很多好的文章也解释的很详细了但我做这道题的心得对于任何一个问题都有他的方法，或许我们不知道這一题他考的是什么内容用什么样的的算法可以解决。这主要原因是我们刷题刷的太少了遇见的少了，碰见一道题不知道用什么样的方法去做这是很恐怖的一件事，所以这就激励我们努力地去刷题没有什么是一成不变的，只要我们肯努力相信有一天我们也会改变，也会有出彩的那一天或许就在不久的将来。

这道题如果就用平常的解法的话你肯定会想到用暴搜，但无疑这样的复杂度太高了必嘫会超限。所以我们就想有没有什么样的方法可以降低时间复杂度呢！这是你可能就想到了字典树字典树可以类似是一棵大树，他有很哆的分支每一个分支下面又包含了许多小的分支，这样他就把复杂的问题简单化了每一个分支都有标记点，很容易找到答案如果有噺的内容要加入，他会在适当的位置把它添加上这样前面很多步骤就优化掉了，从而问题的已解决