子字符串查找算法（BF、KMP、BM、RK）子字符串查找算法（BF、KMP、BM、RK）

98 阅读 0 评论 65 点赞

我是靠谱客的博主闪闪黄豆，最近开发中收集的这篇文章主要介绍子字符串查找算法（BF、KMP、BM、RK）子字符串查找算法（BF、KMP、BM、RK），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

子字符串查找算法（BF、KMP、BM、RK）

BF 子字符串查找算法

在长度为 N 的文本中查找长度为 M 的模式

暴力子字符串查找

指针 i 遍历文本串每次匹配的起始位置
指针 j 遍历模式串中的字符，每次重置为 0
比较文本串中的第 i+j 个字符和模式串中第 j 个字符是否匹配

最坏情况：文本串和模式串都是一连串的A接单个B的形式，则每次都在模式串的最后一个字符处匹配失败。可能的匹配位置为 N - M + 1，每次都需要匹配模式串中的所有字符，则总比较次数为 M(N-M+1)。

// 暴力字符串查找算法
// 可能匹配的位置为: txtLen - patLen + 1
static int BruteForceSubStringSearch(String pat, String txt) {
// 指针 i 跟踪文本串中的单个字符, 表示每次匹配的起始位置
for (int i = 0; i < txtLen - patLen + 1; i++) {
// 指针 j 跟踪模式串中的单个字符
int j;
for (j = 0; j < patLen; j++) {
// 比较文本串中的字符和模式串中的字符是否匹配, 不匹配时跳出循环
// i+j: 文本串中从 i 开始的第 j 个字符
if (txt.charAt(i + j) != pat.charAt(j)) {
break;
}
}
// 如果模式串匹配结束, 则保存该次模式串出现位置的起始下标
if (j == patLen) {
return i;
}
}
return txtLen;
}

显式回退的暴力子字符串查找

指针 i 遍历文本串每次匹配的位置
指针 j 遍历模式串每次匹配的位置
如果匹配，则两个指针同时 +1；

如果不匹配，则文本串指针回退到本次匹配的起始位置，模式串指针回退到模式的开头

// 显式回退的暴力子字符串查找
static int ExplicitFallbackSubStringSearch(String pat, String txt) {
int i, j;
// i 为每次匹配的字符, 等价于上段代码中的i + j
for (i = 0, j = 0; i < txtLen && j < patLen; i++) {
// 文本串中的字符和模式串中的字符串相等时, 文本串和模式串中的指针同时后移
if (txt.charAt(i) == pat.charAt(j)) {
j++;
} else {
// i 在遍历的过程中指针文本中已经匹配的字符序列的末端
// 指针字符不匹配时, 需要同时回退这两个指针
// i-j 指向本次匹配的起始位置, 在下一次循环时指向后一个位置
i -= j;
// j 指向模式的开头
j = 0;
}
}
// 如果模式串匹配结束, 则保存该次模式串出现位置的起始下标
if (j == patLen) {
return i - patLen;
// 未找到匹配
} else {
return txtLen;
}
}

KMP 子字符串查找算法（DFA）

最大前后缀长度

例如串 abcdef：

前缀（不包括尾字符）：a、ab、abc、abcd、abcde
后缀（不包括首字符）：f、ef、def、cdef、bcdef
最大前后缀长度（前缀和后缀中最大的相同串的长度）：0（因为其前缀与后缀没有相同的）

例如串 ababa：

前缀：a、ab、aba、abab
后缀：a、ba、aba、baba
最大前后缀长度：3（aba，长度3）

模式指针的回退

固定文本串不动，从左到右滑动模式字符串直到所有重叠的字符都相互匹配（或没有相匹配的字符）时才停止。在这个过程中，文本指针 i 不会回退，模式指针 j 使用数组 dfa 来更新。

i = i+1

j = dfa[txt.charAt(i)] [j]

dfa[文本串中指针 i 对应的字符 c ] [模式串中的指针 j ]：

文本串的第 i 个字符 c 和模式串的第 j 个字符比较之后，模式串中应该和文本串的下一个(第 i+1 个)字符比较的字符位置
表示比较后模式字符串的指针索引，同时为已匹配字符的个数
匹配时：

文本串：AABAABAAAA

模式串：AABAAA
- txt.charAt(i) == pat.charAt(j)，即模式串的前 j 个字符和文本串对应相同
  
  则应该继续比较模式串和文本串的下一个字符
- j = dfa[txt.charAt(i)] [j] = j+1 ，即文本串的第 i+1 个字符和模式串的第 j+1 个字符比较
不匹配时：

文本串：AABAABAAAA

模式串：AABAAA
- txt.charAt(i) != pat.charAt(j)，即模式串的前 j-1 个字符和文本串对应相同
  
  即已知文本串的 [i-j+1, … , i-1, i] 个字符
- j = dfa[txt.charAt(i)] [j] = 模式串(从位置 1 开始)和文本串(到位置 i 结束)的最大前后缀长度
  
  文本串：AABAABAAAA
  
  模式串： AABAAA
  
  文本串取后缀 [i-j+2, … , i-1, i]，模式串取前缀[1, … , j-1]，找最大前后缀长度

总结：

在匹配失败时，如果模式字符串中的某处可以和匹配失败处的正文相匹配（最大前后缀），那么就不应该完全跳过所有已经匹配的所有字符（i = i-j+1 和 j = 0为跳过）
i = i+1
- 匹配成功：j = dfa[txt.charAt(i)] [j] = j+1
- 匹配失败：j = dfa[txt.charAt(i)] [j] = 模式串和文本串的最大前后缀长度
在匹配失败时总是能够将 j 设为某个值以使 i 不回退
需要提前判断如何重新开始查找，而这种判断只取决于模式本身

匹配失败时，模式串的前 j-1 个字符和文本串对应相同，则由模式串自身可以得到重新回退的位置

KMP查找算法

继续比较的字符指针	文本串 i	模式串 j
匹配成功	i = i+1	j = j+1
匹配失败（暴力）	i = i-j+1	j = 0
匹配失败（KMP）	i = i+1	j = dfa[txt.charAt(i)] [j]

为什么使用 dfa[] [] 记录指针 j 后，指针 i 不用回退？

当 i 和 j 所指向的字符匹配失败时，如果是从文本串 i-j+1 处（模式串头部）开始继续检查匹配情况

则文本串中可能和模式串匹配的下一个位置应该为 i-dfa[txt.charAt(i)] [j]

又文本串中从该位置开始的 dfa[txt.charAt(i)] [j] 个字符和模式串的前 dfa[txt.charAt(i)] [j] 应该相同

因此将 j 设为 dfa[txt.charAt(i)] [j] 后，模式串的前 j 个字符和文本串已经匹配，

则无需回退指针 i ，只需要将 i 设为 i+1 ，继续比较即可

这与指针 i 和 j 所指向的字符匹配成功时的行为相同

DFA模拟

DFA（确定有限状态自动机）：

每个模式字符串都对应着一个自动机（由保存了所有转换的 dfa[] [] 数组表示）
状态：数字标记的圆圈（每个状态都表示模式字符串中的索引值）

开始状态：0

中间状态 j ：表示已经有 j 个字符匹配

停止状态：M (模式串的长度)，不会进行任何转换
转换：带标签的箭头（文本串对应字母表中的每个字符）

只有一条是匹配转换（即从 j 到 j+1，标签为 pat.charAt(j)）

其他的都是非匹配转换（指向左侧）

所有状态转换都和字符比较相对应

自动机运行过程：

从状态 0 开始，每次从左向右在文本中读取一个字符并移动到一个新的状态
停留在状态 0 并扫描文本，直到找到一个和模式首字母相同的字符，移动到下一个状态并开始运行
当状态 j 检查文本中的第 i 个字符时，沿着转换 dfa[txt.charAt(i)] [j] 前进
- 匹配转换：j = dfa[txt.charAt(i)] [j] = j+1，向右移动进入下一个状态
  
  等价于增大模式字符串的指针 j
- 非匹配转换：j = dfa[txt.charAt(i)] [j] = 最大前后缀长度，向左移动回到较早的状态
  
  等价于将模式字符串的指针 j 变为一个较小值
并继续检查下一个字符（i+1）
结果判断
1. 到达状态 M ：识别到该模式（从文本中找到了和模式相匹配的一段子字符串）
2. 文本结束时未达到状态M，则文本中不存在匹配该模式的子字符串

KMP子字符串查找算法（DFA模拟）：

// 在 txt 中找到 pat 的出现位置
public int search(String txt){
int i, j, N = txt.length(), M = pat.length();
for(i=0, j=0; i<N && j<M;i++){
j = dfa[txt.charAt(i)][j];
}
// 找到匹配
if(j==M){
return i-M;
// 未找到匹配
}else{
return N;
}
}

总结：

正文指针 i 从左向右移动，每次一个字符
模式指针 j 在 DFA 的指导下在模式字符串中左右移动

构造DFA

如何计算给定模式相对应的 dfa[] [] 数组？

答案： DFA 本身，在计算 DFA 的第 j 个状态(dfa[] [j])时，此时DFA的前 j-1 个状态(dfa[] [0, j-1])已经处理完成，并由状态 X 记录在状态 j-1 时的最大匹配状态或最大前后缀长度，用之前进行的状态转换 dfa[] [X] 来更新 dfa[] [j]，并根据当前字符 j 来更新匹配时的状态转换 (j+1) 和识别当前字符 j 之后的最大匹配状态或最大前后缀长度，在下次构造时为重启状态。

例如：

文本串：ABABAB ABABAB A BABA B AB ABA B AB ABA B i = 5

模式串：ABABAC ABABAC ABABAC ABABAC ABA BAC j = 5

① ② ③ ④ ⑤

当在 pat.charAt(j) 处匹配失败时（①），通常做法是将文本指针回退到最开始匹配的位置（②），并在右移一位后重新扫描已知的文本字符（③），但我们并不想回退，只想将DFA重置到适当的状态（④），等价于文本指针回退。

此时 i = 5，j = 5，是在 j-1=4 处匹配成功后（即文本串[i-j+1, i-1]和模式串[0, j-1]相同）进行的

对于匹配失败的这段文本串 [i-j+1, i]，由于模式需要右移一位继续匹配，所以忽略首字母：

又由于文本串的最后一个字符匹配失败，所以忽略尾字母：

则只需要扫描文本串 pat.charAt(1) 到 pat.charAt(j-1) 之间的文本字符，而这段字符和模式串又完全相同

这些字符在模式串中都是已知的，因此对于每个可能匹配失败的位置都可以预先找到重启DFA的正确状态（即根据模式串自身求最大前后缀）

当 i = 4, j = 4 时，文本串和模式串完全匹配（ABABA）

计算重启状态（模式串的最大前后缀长度）
- 前缀：A, AB, ABA, ABAB
- 后缀：A, BA, ABA, BABA
- 最大前后缀长度：3 (ABA)
最大前后缀为之前处理过的字符串
j = 5 时匹配失败（①）
右移一位后需要重新扫描的文本字符为 BABA （③）
首字母匹配失败后继续右移扫描 ABA （④）
匹配成功，此时 j=3（重启状态 X=3），等价于重置到状态 3 （⑤）
因此 dfa[] [5] = dfa[] [3]，i = i+1 继续匹配

KMP 子字符串查找算法中由模式字符串构造 DFA ：

dfa[自动机中的标签字符 c ] [自动机中的状态 j ]：

重启状态 X，也可理解为模式串当前字符还未识别时的最大匹配状态（最大前后缀长度）

从状态 0 开始，当要识别的字符和模式串的首字符(pat.charAt(0))相同时，进入状态 1

dfa[pat.charAt(0)][0] = 1;

重启状态 X 从 0 开始，从状态 1 继续构造 dfa[] [j]，直到达到停止状态 M
在计算 DFA 的第 j 个状态(dfa[] [j])时，此时DFA的前 j-1 个字符(dfa[] [0, j-1])已经处理完成

X 为状态 j-1 (识别到第 j-1 个字符) 时的最大匹配状态(模式串 [0, j-1] 的最大前后缀长度)

则说明之前的 DFA 中已经对该状态做过转换，因此对该状态对应的 dfa[] [X]，遍历所有字符后，等价于对当前第 j 个字符进行的所有转换 dfa[] [j]（包括匹配转换和非匹配转换）
```
for(int c=0; c<R; c++){
dfa[c][j] = dfa[c][X];
}
```
再根据模式串当前字符更新状态 j 匹配成功时的状态转换

状态 j 同时为索引 j，即在状态 j 时要识别的字符为模式串中该索引位置的字符时，进行匹配转换
```
dfa[pat.charAt(j)][j] = j+1;
```
由于状态 X 处的状态转换已经完成（包含当前字符的情况）

如果当前字符为状态 X 处的匹配转换，则 X+1（在之前已经完成，表示最大匹配状态 +1 或最大前后缀长度+1）

如果为非匹配转换，则根据该状态 X 以及当前字符可以进行状态回退
```
X = dfa[pat.charAt(j)][X];
```
则 dfa[pat.charAt(j)] [X] 为在状态 X 时遇到当前字符 j 后的状态转换

更新后的状态 X 表示识别当前字符后的最大匹配状态或最大前后缀长度

重启状态即为回到之前的最大匹配状态

// 根据模式字符串构造 DFA
public KMP(String pat){
int M = pat.length();
// ASCII 码中所有可能的字符
int R = 256;
// 对每个状态，遍历字母表中的每个字符，实现 DFA
dfa = new int[R][M];
// 从状态 0 开始，要识别的字符和模式串的首字符(pat.charAt(0))相同时，进入状态 1
dfa[pat.charAt(0)][0] = 1;
// 重启状态 X 从 0 开始，从状态 1 继续构造 dfa[][j]
for(int X=0, j=1; j<M; j++){
// 文本串中所有可能的字符，先生成所有字符匹配失败时的重启状态
for(int c=0; c<R; c++){
// 复制匹配失败时的值，j 位置的不同字符有不同的状态转换
dfa[c][j] = dfa[c][X];
}
// 设置匹配成功情况下的值，会重置之前循环中该字符的重启状态
dfa[pat.charAt(j)][j] = j+1;
// 处理第 j 列时，用当前的模式串字符更新重启状态（最大前后缀长度）
X = dfa[pat.charAt(j)][X];
}
}

优点：

适合查找自我重复性的模式字符串
不需要再输入中回退
适合在长度不确定的输入流中进行查找

完整的 KMP 代码

public class KMP{
private String pat;
private int[][] dfa;
// 根据模式字符串 pat 创建DFA
public KMP(String pat){
this.pat = pat;
int M = pat.length();
// ASCII 码中所有可能的字符
int R = 256;
// 对每个状态，遍历字母表中的每个字符，实现 DFA
dfa = new int[R][M];
// 从状态 0 开始，要识别的字符和模式串的首字符(pat.charAt(0))相同时，进入状态 1
dfa[pat.charAt(0)][0] = 1;
// 重启状态 X 从 0 开始，从状态 1 继续构造 dfa[][j]
for(int X=0, j=1; j<M; j++){
// 文本串中所有可能的字符，先生成所有字符匹配失败时的重启状态
for(int c=0; c<R; c++){
// 复制匹配失败时的值，j 位置的不同字符有不同的状态转换
dfa[c][j] = dfa[c][X];
}
// 设置匹配成功情况下的值，会重置之前循环中该字符的重启状态
dfa[pat.charAt(j)][j] = j+1;
// 处理第 j 列时，用当前的模式串字符更新重启状态（最大前后缀长度）
X = dfa[pat.charAt(j)][X];
}
}
// 在 txt 中找到 pat 的出现位置, 即在 txt 上模拟 DFA 的运行
public int search(String txt){
int i, j, N = txt.length(), M = pat.length();
for(i=0, j=0; i<N && j<M;i++){
j = dfa[txt.charAt(i)][j];
}
// 找到匹配
if(j==M){
return i-M;
// 未找到匹配
}else{
return N;
}
}
}

KMP 子字符串查找算法（next 数组）

匹配过程：s[i] 和 p[j+1]

当不匹配时，则 s[i-1] 和 p[j] 已匹配，求 next[j]，则求相等的最大前后缀，并继续匹配
next[i] = j

p[1, j] = p[i-j+1, i]（模式串中以 i 为终点的后缀和从头开始的前缀相等）且长度最大

等价于模式串自身进行匹配

public class KMP_AC {
// 字符串
static String str;
// 模式串
static String pat;
// 字符串长度
static int strLen;
// 模式串长度
static int patLen;
// next 数组
static int[] next;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
patLen = Integer.parseInt(sc.nextLine());
pat = " " + sc.nextLine();
strLen = Integer.parseInt(sc.nextLine());
str = " " + sc.nextLine();
// 下标从1开始
next = new int[patLen + 1];
// 求next数组，next[1]=0 (第一个字符匹配失败则从 0 开始)
//模板串自身进行匹配(与 KMP 匹配过程类似)
for (int i = 2, j = 0; i <= patLen; i++) {
// j 没有退回起点并且对应回退字符不匹配
while (j != 0 && pat.charAt(i) != pat.charAt(j + 1)) {
j = next[j];
}
// 字符匹配，继续比较
if (pat.charAt(i) == pat.charAt(j + 1)) {
j++;
}
// 保存 next 数组值
next[i] = j;
}
// KMP匹配过程，s[i] 和 p[j+1] 进行匹配
for (int i = 1, j = 0; i <= strLen; i++) {
// j没有退回起点并且对应回退字符不匹配
while (j != 0 && str.charAt(i)!=pat.charAt(j+1)) {
// 寻找 p 的最大后缀等于前缀(最小移动距离)
// 模板串向后移动， j 下标在模板中向前移动(可能退回起点)
j = next[j];
}
// j 退回起点或字符匹配，则继续比较
if (str.charAt(i) == pat.charAt(j + 1)) {
j++;
}
// 匹配成功
if (j == patLen) {
// 输出出现位置的起始下标(从0开始)
System.out.print(i - patLen + " ");
// 达到模板最大长度，回退到最大后缀位置，继续匹配下一个子串
j = next[j];
}
// 都不满足，则i++，从主串的下一字符开始匹配
}
}
}

BM 字符串查找算法

启发式地处理不匹配的字符。

当可以在文本字符串中回退时，从右向左 扫描模式串并将它和文本匹配。

一般来说，模式的结尾部分也可能出现在文本的其他位置，因此也需要一个记录重启位置的数组。

根据匹配失败时文本串的当前字符和模式中是否包含该字符来决定下一步的行动。

预处理步骤的目的：判断对于文本中可能出现的每一个字符，在匹配失败时算法应该怎么办

起点

数组 right[] 记录重启位置

含义
- 记录字母表中的每个字符在模式中出现的最靠右的地方
- 如果字符在模式中不存在则表示为 -1
- 表示如果该字符出现在文本中且在查找时造成了一次匹配失败，i 应该向右跳跃多远
- 跳跃表
初始化
- 初始化所有元素为 -1，表示模式串中不含该字符
- 然后对于 0 到 M-1 的 j，将 right[pat.charAt(j)] = j （以该字符最后一次在模式串中出现的位置为最终结果）
举例

N E E D L E
1. 遍历字母表中的所有字母：right[0, 256] = -1
2. 遍历模式串中的所有字母：right[pat.charAt(j)] = j
  
  right[N] = 0; right[E] = 1; right[E] = 2; right[D] = 3; right[L] = 4; right[E] = 5
3. 模式串字符出现的最右位置（最后一次）会重置之前的结果
  
  right[N] = 0; right[D] = 3; right[L] = 4; right[E] = 5

子字符串的查找

索引 i 在文本中从左向右 [0, N-M] 移动

索引 j 在模式中从右向左 [M-1, 0] 移动

内循环检查文本串的第 i+j 个字符和模式串第 j 个字符是否一致

匹配成功：

从 M-1 到 0 的所有 j ，txt.charAt(i+j) 都和 pat.charAt(j) 相等

此时 i 的位置即为子字符串的起始位置

匹配失败：

如果造成匹配失败的字符不包含在模式串中，将模式串向右移动 j+1 个位置（即将 i 增加 j+1）

j+1 为模式串的当前索引到头部的长度，小于这个偏移量只能使该字符与模式中还未匹配的某个字符重叠
如果造成匹配失败的字符包含在模式串中，则可以使用 right[] 数组来将模式串和文本对齐，

使得该字符和它在模式串中出现的最右位置相匹配

小于这个偏移量只能使该字符和模式串中的与它无法匹配的而字符（比它出现的最右位置更靠右的字符）重叠
如果该方式无法增大 i，那就直接将 i 加 1 来保证模式串至少向右移动了一个位置

匹配失败时该字符在模式串中出现的最右位置大于模式串的当前指针 j ，

则 j-right[txt.charAt(i+j)] ≤ 0，对齐会导致模式串和文本串指针 i 向左移动（之前匹配失败的情况）

因此 i 必须增大以进行下一次匹配

i += j-right[txt.charAt(i+j)] 说明：

j 是匹配失败时，模式串指针的当前索引（从右向左：右侧已匹配，左侧未匹配）
txt.charAt(i+j) 为匹配失败时文本串中的当前字符
- 如果该字符包含在模式串中
  - right[txt.charAt(i+j)] 为文本串中该字符在模式串中出现的最右索引
  - j-right[txt.charAt(i+j)] 为将模式串中的该字符移动到当前索引所需的最小偏移量
- 如果该字符不包含在模式串中
  - right[txt.charAt(i+j)] = -1
  - j-right[txt.charAt(i+j)] = j+1 为将模式串的剩余字符全部移开所需的最小偏移量
模式串向右移动进行对齐等价于文本串指针右移和模式串头部进行对齐

public class BoyerMoore{
private int[] right;
private String pat;
// 计算跳跃表
BoyerMoore(String pat){
this.pat = pat;
int M = pat.length();
int R = 256;
right = new int[R];
// 不包含在模式串的中字符的值为-1
for(int c=0; c<R; c++){
right[c] = -1;
}
// 包含在模式串中的字符的值为它在其中出现的最右位置
for(int j=0; j<M; j++){
right[pat.charAt(j)] = j;
}
}
// 在 txt 中查找模式串
public int search(String txt){
int N = txt.length();
int M = pat.length();
// 文本串指针每次的跳跃距离
int skip;
// 文本串指针从左向右扫描
for(int i=0; i<=N-M; i+=skip){
skip = 0;
// 模式串指针从右向左扫描
for(int j=M-1; j>=0; j--){
// 匹配失败
if(pat.charAt(j) != txt.charAt(i+j)){
// 计算跳跃距离
skip = j- right[txt.charAt(i+j)];
// 模式串回到之前匹配失败过的状态，强制向后移动一位
if(skip<1){
skip = 1;
}
break;
}
}
// 当模式串字符全部匹配成功时，skip为初始值，则说明找到匹配
if(skip ==0) return i;
}
// 未找到匹配
return N;
}
}

优点：

预计算了模式串和自身的不匹配情况，并未最坏情况提供了先行级别的运行时间保证
启发式地处理不匹配的字符

RK指纹字符串查找算法

指纹即散列值

基于散列的而字符串查找算法

计算模式串的散列函数，然后用相同的散列函数计算文本中所有可能的 M 个字符的子字符串散列值并寻找匹配。如果找到了一个散列值和模式串相同的子字符串，那么再继续验证两者是否匹配。

即将模式保存在一张散列表中，然后在文本的所有子字符串中进行查找。但不需要为散列表预留任何空间，因为它只含一个元素。

计算散列值会涉及字符串中的每个字符，成本即直接比较这些字符（暴力字符串查找）要高得多。

在常数时间内算出 M 个字符的子字符串散列值的方法，实际运行时间为线性级别。

基本思想

长度为 M 的字符串对应着一个 R 进制的 M 位数。（字符串长度和位数相对应）

例如：对于数字字符串 26535，长度为 5，进制为 10，对应 5 位数字26535

为了用一张大小为 Q 的散列表（数组）来保存这种类型的键，需要一个能够将 R 进制的 M 位数转化为一个 0 到 Q-1 之间（索引）的 int 值散列函数。

除留余数法：将该数除以 Q 并取余。Q 为在不溢出的情况下选择的一个尽可能大的素数。

并不会真的需要一张散列表。

计算字符串的散列函数

将字符串当作较大整数

Java 的 charAt() 函数能够返回一个 char 值（一个非负 16 位整数）

如果 R 比任何字符的值都大，则相当于将字符串当作一个 M 位的 R 进制值，将它除以 Q并取余。

Horner 方法散列字符串键：M 次乘法、加法和取余与来计算一个字符串的散列值。只要 R 足够小，不造成溢出，那么结果就能落在 0 至 Q-1 之间。

// 计算 R 进制的字符串 key[0..M-1] 的散列值，O(M)
public long hash(String key, int M){
long h = 0;
// 对于该数字串的每一位数字，将散列值乘以 R，加上该位数字，除以 Q 并取余数
for(int j=0; j<M; j++){
h = (R * h + key.charAt(j)) % Q;
}
return h;
}

成本：对文本中的每个字符进行乘法、加法和取余计算的成本之和，最坏情况下需要NM次操作（对文本串的每位，做 M 次运算）

关键思想

对于所有位置 i ，高效计算文本中 i+1 位置的子字符串散列值

计算过程：

t_i 表示 txt.charAt(i)
文本 txt 中起始于位置 i 的含有 M 个字符的子字符串所对应的数：
- x_i = t_iR^M-1 + t_i+1R^M-2 + ··· + t_i+M-1R⁰
h(x_i) = x_i mod Q
将模式串右移一位等价于将 x_i 替换为 x_t+1 = (x_t - t_iR^M-1)R + t_i+M

即将它减去第一个数字的值，乘以 R，再加上最后一个数字的值

取余操作的性质：

如果在每次算数操作之后都将结果除以 Q 并取余，等价于在完成了所有算术操作之后再将最后的结果除以 Q 并取余
即不需要保存中间结果，只需要保存他们除以 Q 之后的余数

RK 指纹字符串查找算法

public class RabinKarp{
// 模式串的散列值
private long patHash;
// 模式串的长度
private int M;
// 一个很大的素数
private long Q;
// 字母表（进制）的大小
private int R = 256;
// 保存 R^M-1 % Q
private long RM;
public RabinKarp(String pat){
this.M = pat.length();
// Q 为随机素数
Q = longRandomPrime();
RM = 1；
// 计算最高位的进制幂 R^(M-1) % Q
for(int i=1; i<=M-1; i++){
// 用于减去第一个数字时的计算
RM = (R * RM) % Q;
}
patHash = hash(pat, M);
}
// 计算 R 进制的字符串 key[0..M-1] 的散列值，O(M)
public long hash(String key, int M){
long h = 0;
// 对于该数字串的每一位数字，将散列值乘以 R，加上该位数字，除以 Q 并取余数
for(int j=0; j<M; j++){
h = (R * h + key.charAt(j)) % Q;
}
return h;
}
// 在文本中查找相等的散列值
private int search(String txt){
int N = txt.length();
// 计算文本的前 M 个字母的散列值 xi
long txtHash = hash(txt, M);
// 一开始就匹配成功
if(patHash == txtHash){
return 0
}
// 计算位置 i 开始的 M 个字符的散列值
// 减去第一个数字， 加上最后一个数字， 再次检查匹配
for(int i=M; i<N; i++){
// 额外加上一个 Q 保证所有数均为正
// 减去第一个数字：x_i - R^M-1 * t_i-M
txtHash = (txtHash + Q - RM * txt.charAt(i-M) % Q) % Q;
// 加上最后一个数字：* R + ti
txtHash = (txtHash * R + txt.charAt(i)) % Q;
// 找到匹配
if(patHash = txtHash){
return i - M + 1;
}
}
// 未找到匹配
return N;
}
}

用蒙特卡洛法验证正确性

在文本 txt 中找到散列值与模式串相匹配的一个 M 个字符的子字符串之后，可以逐个比较字符以确保得到了一个匹配而非相同的散列值，但需要回退文本指针。

替代方法：将散列表的”规模“ Q 设为任意大（大于10²⁰的long）的一个值，使得一个随机键的散列值与模式串冲突的概率小于 10²⁰ 。

只要选择了适当的 Q 值，随机字符串产生散列碰撞的概率为 1/Q。即对于实际可能出现的值，字符串不匹配时散列值也不会匹配，散列值匹配时字符串才会匹配。

最后

以上就是闪闪黄豆为你收集整理的子字符串查找算法（BF、KMP、BM、RK）子字符串查找算法（BF、KMP、BM、RK）的全部内容，希望文章能够帮你解决子字符串查找算法（BF、KMP、BM、RK）子字符串查找算法（BF、KMP、BM、RK）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：算法总结
浏览次数：98 次浏览
发布日期：2023-11-30 13:45:08
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_10_f4_14__7__26_x.html

子字符串查找算法（BF、KMP、BM、RK）子字符串查找算法（BF、KMP、BM、RK）

概述

子字符串查找算法（BF、KMP、BM、RK）

BF 子字符串查找算法

暴力子字符串查找

显式回退的暴力子字符串查找

KMP 子字符串查找算法（DFA）

最大前后缀长度

模式指针的回退

KMP查找算法

DFA模拟

DFA（确定有限状态自动机）：

自动机运行过程：

KMP子字符串查找算法（DFA模拟）：

构造DFA

如何计算给定模式相对应的 dfa[] [] 数组？

KMP 子字符串查找算法中由模式字符串构造 DFA ：

完整的 KMP 代码

KMP 子字符串查找算法（next 数组）

BM 字符串查找算法

起点

子字符串的查找

RK指纹字符串查找算法

基本思想

计算字符串的散列函数

关键思想

RK 指纹字符串查找算法

用蒙特卡洛法验证正确性

最后

评论列表共有 0 条评论

发表评论取消回复

子字符串查找算法（BF、KMP、BM、RK）子字符串查找算法（BF、KMP、BM、RK）

概述

子字符串查找算法（BF、KMP、BM、RK）

BF 子字符串查找算法

暴力子字符串查找

显式回退的暴力子字符串查找

KMP 子字符串查找算法（DFA）

最大前后缀长度

模式指针的回退

KMP查找算法

DFA模拟

DFA（确定有限状态自动机）：

自动机运行过程：

KMP子字符串查找算法（DFA模拟）：

构造DFA

如何计算给定模式相对应的 dfa[] [] 数组？

KMP 子字符串查找算法中由模式字符串构造 DFA ：

完整的 KMP 代码

KMP 子字符串查找算法（next 数组）

BM 字符串查找算法

起点

子字符串的查找

RK指纹字符串查找算法

基本思想

计算字符串的散列函数

关键思想

RK 指纹字符串查找算法

用蒙特卡洛法验证正确性

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复