前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决,但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了,记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。
简介
Trie树百度百科解释如下:又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
图中红色的点代表此处有字符串在此结束,上图中共有7个字符串:abc、abcd、abd、b、bcd、efg、hij(百科中的图,空白边就算作j好了)。
Trie树的使用场景
- 字符串检索,词频统计,搜索引擎的热门查询。
- 字符串最长公共前缀。
- 字符串排序。
- 作为其他数据结构和算法的辅助结构,如后缀树,AC自动机等。
至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现,就算能实现也需要大量的改变。