Content #
在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。把主串的长度记作 n，模式串的长度记作 m。因为是在主串中查找模式串，所以 n>m。
算法的思路：通过哈希算法对主串中的起始位置分别是 0、1、2….n-m 且长度为 m 的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
假设要匹配的字符串的字符集中只包含 K 个字符，可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。
比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。
相邻两个子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，也就是说，我们可以使用 s[i-1]的哈希值很快的计算出 s[i]的哈希值。
\[h[i-1]=26^{m-1}\times (S[i-1]-‘a’)+26^{m-2}\times (s[i]-‘a’)+\cdots + 26^0\times (S[i+m-2]-‘a’)\] \[h[i]=26^{m-1}\times (S[i]-‘a’)++\cdots +26^1\times (s[i+m-2]-‘a’) + 26^0\times(S[i+m-1]-‘a’)\] 由此可知： \[h[i]=(h[i-1]-26^{m-1} \times (s[i-1] - ‘a’)) \times 26 + 26^0 \times (s[i+m-1]-‘a’)\]
26^(m-1) 这部分的计算，我们可以通过查表的方法来提高效率。我们事先计算好 26^0、26^1、26^2……26^(m-1)，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。
整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。
第一部分，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。
Viewpoints #
From #
32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？