二十四、字符串

1.Rabin-Karp算法

访问 www.coding-time.cn 阅读原文动画效果，体验更佳。

在计算机科学中，Rabin-Karp算法（或Karp-Rabin算法）是一种使用散列（哈希）的字符串搜索算法，由Richard M. Karp和Michael O. Rabin（1987年）创建。

1）算法

Rabin-Karp算法通过使用哈希函数加速模式与文本中的子字符串的相等性测试。哈希函数是将每个字符串转换为其哈希值的数值的函数；例如，我们可以有hash('hello') = 5。

该算法利用了这样一个事实：如果两个字符串相等，则它们的哈希值也相等。因此，字符串匹配（几乎）可以简化为计算搜索模式的哈希值，然后在具有该哈希值的输入字符串的子字符串中寻找匹配。

然而，这种方法存在两个问题。首先，由于存在大量不同的字符串和较少的哈希值，一些不同的字符串将具有相同的哈希值。如果哈希值匹配，模式和子字符串可能不匹配；因此，必须通过比较它们来确认搜索模式和子字符串的潜在匹配；对于较长的子字符串，这种比较可能需要很长时间。

幸运的是，对于合理的字符串，良好的哈希函数通常不会产生太多冲突，因此期望的搜索时间将是可接受的。

2）使用的哈希函数

Rabin-Karp算法的性能关键在于高效计算文本的连续子字符串的哈希值。Rabin指纹是一种流行且有效的滚动哈希函数。

本示例中描述的多项式哈希函数不是Rabin指纹，但它同样有效。它将每个子字符串视为一些基数的数字，基数通常是一个大素数。

3）复杂度

对于长度为n的文本和p个总长度为m的模式，其平均和最佳情况下的运行时间为O(n + m)，空间复杂度为O(p)，但最坏情况下的运行时间为O(n * m)。

4）应用

该算法的一个实际应用是检测抄袭。给定源材料，该算法可以快速搜索论文中来自源材料的句子，忽略大小写和标点等细节。由于所寻找的字符串非常丰富，单字符串搜索算法是不实际的。

5）参考资料

• Wikipedia
  
• YouTube编辑距离
  

2.编辑距离

编辑距离（Levenshtein distance）是一种衡量两个序列之间差异的字符串度量。简单地说，编辑距离是将一个字符串转换为另一个字符串所需的最少单字符编辑（插入、删除或替换）次数。

1）定义

数学上，两个字符串 a 和 b（长度分别为 |a| 和 |b|）之间的编辑距离由下式给出：

其中， 是指示函数，当 时等于 0，否则等于 1， 而 是字符串 a 的前 i 个字符和字符串 b 的前 j 个字符之间的距离。

注意，最小值中的第一个元素对应删除（从 a 到 b），第二个元素对应插入，第三个元素对应匹配或不匹配，具体取决于相应的符号是否相同。

2）示例

例如，字符串 kitten 和 sitting 之间的编辑距离为 3，因为以下三个编辑操作将一个字符串变成另一个字符串，而没有办法少于三个编辑操作：

• kitten → sitten（用 "s" 替换 "k"）
  
• sitten → sittin（用 "i" 替换 "e"）
  
• sittin → sitting（在末尾插入 "g"）。
  

3）应用

编辑距离在许多应用中都有广泛的应用，例如拼写检查器、光学字符识别纠错系统、模糊字符串搜索以及基于翻译记忆的自然语言翻译辅助软件。

带你读《图解算法小抄》二十四、字符串（2）https://developer.aliyun.com/article/1347818?groupCode=tech_library