首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    trie树(字典树)-HDU1251

    举一个例子,给50000个由小写字母构成的长度不超过10的单词,然后问某个公共前缀是否出现过。如果我们直接从字符串集中从头往后搜,看给定的字符串是否为字符串集中某个字符串的前缀,那样复杂度为O(50000^2),这样显然会TLE。又或是我们对于字符串集中的每个字符串,我们用MAP存下它所有的前缀。然后询问时可以直接给出结果。这样复杂度为O(50000*len),最坏情况下len为字符串最长字符串的长度。而且这没有算建立MAP存储的时间,也没有算用MAP查询的时间,实际效率会更低。但如果我们用trie的话,当查询如字符串abcd是否为某字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。实际查询复杂度只有O(len),建立trie的复杂度为O(50000).这是完全可以接受的。

    01
    领券