前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决，但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了，记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。

简介

Trie树百度百科解释如下：又称单词查找树，字典树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie树的直观结构如图所示：

图中红色的点代表此处有字符串在此结束，上图中共有7个字符串：abc、abcd、abd、b、bcd、efg、hij（百科中的图，空白边就算作j好了）。

Trie树的使用场景

• 字符串检索，词频统计，搜索引擎的热门查询。
• 字符串最长公共前缀。
• 字符串排序。
• 作为其他数据结构和算法的辅助结构，如后缀树，AC自动机等。

至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现，就算能实现也需要大量的改变。

阅读全文>>

Levenshtein距离，又称为编辑距离，或者成为字符串相似度，意思是一个字符串转换为另一个字符串所需要的最小编辑次数。编辑包含：插入、删除和替换三种操作。例如字符串：yurnom和yunum的编辑距离为2，因为需要插入一个r和将u替换为o两次操作。

Levenshtein算法由俄罗斯科学家Vladimir Levenshtein在1965年提出，该算法现在广泛用于DNA匹配、字符串纠错、实体共指等领域。

算法简介

将2个字符串转换为一个矩阵，为了简单起见，采用字符串heqi和hoi。转换后进行初始化，如下所示：

其中数字部分为初始化的值，现计算绿色格子A处的值，其算法为：

1. 若A所对应的两个字符相同，则左上角蓝色格子的值+0，否则+1，结果记为R1
2. 选取上方和左方紫色格子中较小的值，并+1，结果记为R2
3. 选取R1和R2中的较小值为绿色格子A处的值

经过计算可以得出A处的值为0，当A处计算完毕后，其右方和下方的值可以接着进行计算了，如此整个矩阵的值将可全部计算出来。最后矩阵右下方红色格子的值即为两个字符串的编辑距离。

至于为何左方和上方的值加1、左上角的值根据不同的情况加0或1的原因（也就是这么算的原理）比较简单，在此不再详述。

阅读全文>>