【算法2-4】字符串

对应进阶篇第 7 章。 字符串，就是由字符连接而成的序列。我们可以使用不同的算法来解决不同的和字符串有关 的问题。《基础篇》中介绍过的哈希表，可以将一个字符串映射为一个整数，可以高效地查询这 个字符串是否存在于一个集合中。本章介绍另外两种比较基础的字符串工具——Knuth-Morris-Pratt 算法和字典树。 Knuth-Morris-Pratt 算法，简称 KMP 算法，可以高效的从一个字符串中查询另外一个指定的 字符串是否存在；如果存在的话位置在哪里。它会利用字符串匹配过程中失败的信息，从而减少 字符串查找比较的次数。 而字典树，又称为 Trie 树，可以方便的储存、索引和查找字符串。当然除了字符串，还可以 将数字拆成二进制，存入字典树中，常常可以高效处理涉及到异或的问题。