Knuth-Morris-Pratt 算法
用于模式匹配的 KMP 算法
KMP 算法用于解决模式匹配问题，即在文本中查找给定模式的所有出现位置。它在查找多个模式时非常有用。例如，如果文本为"aabbaaccaabbaadde"，模式为"aabaa"，则该模式在文本中出现两次，分别位于索引 0 和 8 处。
此问题的简单解决方案是将模式与文本中所有可能的子字符串进行比较，从最左边的位置开始向右移动。这需要 O(n*m) 的时间复杂度，其中 n 是文本的长度，m 是模式的长度。
当我们处理长文本文档时，暴力破解和简单方法可能会导致冗余比较。为了避免这种冗余，Knuth、Morris 和 Pratt 开发了一种线性序列匹配算法，称为 KMP 模式匹配算法。它也被称为 Knuth Morris Pratt 模式匹配算法。
KMP 算法的工作原理是什么？
KMP 算法从左到右开始搜索操作。它使用 prefix 函数 来避免在搜索模式时进行不必要的比较。此函数存储迄今为止匹配的字符数，称为 LPS 值。KMP 算法涉及以下步骤 −
定义前缀函数。
将模式滑到文本上进行比较。
如果所有字符都匹配，则我们找到了匹配项。
如果不是，请使用前缀函数跳过不必要的比较。如果不匹配字符的前一个字符的 LPS 值为"0"，则从模式的索引 0 开始与文本中的下一个字符进行比较。但是，如果 LPS 值大于"0"，则从等于前一个不匹配字符的 LPS 值的索引值开始比较。
KMP 算法的时间复杂度为 O(n + m)，空间复杂度为 O(m)。它比朴素解决方案更快，因为它跳过了冗余比较，并且最多只比较文本中的每个字符一次。
让我们通过一个例子来理解模式匹配问题的输入输出场景 −
输入： 主字符串："AAAABCAAAABCBAAAABC" 模式："AAABC" 输出： 在以下位置找到图案： 1 在以下位置找到图案： 7 在以下位置找到图案： 14
示例
以下示例实际演示了用于模式匹配的 KMP 算法。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// 查找前缀的函数
void prefixSearch(char* pat, int m, int* pps) {
int length = 0;
// 存储前缀的数组
pps[0] = 0;
int i = 1;
while(i < m) {
// 检查当前字符是否与前一个字符匹配
if(pat[i] == pat[length]) {
// 增加长度
length++;
// 将长度存储在前缀数组中
pps[i] = length;
}else {
if(length != 0) {
// 更新前一个前缀的长度
length = pps[length - 1];
i--;
} else
// 如果长度为 0，则将 0 存储在前缀数组中
pps[i] = 0;
}
i++; // incrementing i
}
}
// 搜索模式的函数
void patrnSearch(char* orgnString, char* patt, int m, int *locArray, int *loc) {
int n, i = 0, j = 0;
n = strlen(orgnString);
// 用于存储前缀值的数组
int* prefixArray = (int*)malloc(m * sizeof(int)); // 为前缀数组分配内存
// 调用前缀函数填充前缀数组
prefixSearch(patt, m, prefixArray);
*loc = 0; // 初始化位置索引
while(i < n) {
// 检查主字符串字符是否与模式字符串字符匹配
if(orgnString[i] == patt[j]) {
// 增加 i 和 j
i++;
j++;
}
// 如果 j 和 m 相等，则找到模式
if(j == m) {
// 存储图案的位置
locArray[*loc] = i-j;
(*loc)++; // 增加位置索引
// 将 j 更新为前一个前缀值
j = prefixArray[j-1];
// 检查 i 是否小于 n 并且当前字符不匹配
}else if(i < n && patt[j] != orgnString[i]) {
if(j != 0)
// 将 j 更新为前一个前缀值
j = prefixArray[j-1];
// if j is zero
else
i++; // increment i
}
}
free(prefixArray); // free the memory of the prefix array
}
int main() {
// 声明原文
char* orgnStr = "AAAABCAEAAABCBDDAAAABC";
// 找到模式
char* patrn = "AAABC";
// get the size of the pattern
int m = strlen(patrn);
// 用于存储图案位置的数组
int locationArray[strlen(orgnStr)];
// to store the number of locations
int index;
// 调用模式搜索功能
patrnSearch(orgnStr, patrn, m, locationArray, &index);
// 循环遍历位置数组
for(int i = 0; i<index; i++) {
// 打印图案的位置
printf("在以下位置发现图案： %d
", locationArray[i]);
}
}
#include<iostream>
using namespace std;
// 查找前缀的函数
void prefixSearch(string pattern, int m, int storePrefx[]) {
int length = 0;
// 存储前缀的数组
storePrefx[0] = 0;
int i = 1;
while(i < m) {
// 检查当前字符是否与前一个字符匹配
if(pattern[i] == pattern[length]) {
// 增加长度
length++;
// 将长度存储在前缀数组中
storePrefx[i] = length;
}else {
if(length != 0) {
// 更新前一个前缀的长度
length = storePrefx[length - 1];
i--;
} else
// 如果长度为 0，则将 0 存储在前缀数组中
storePrefx[i] = 0;
}
i++; // incrementing i
}
}
// 搜索模式的函数
void patrnSearch(string orgnString, string patt, int *locArray, int &loc) {
int n, m, i = 0, j = 0;
n = orgnString.size();
m = patt.size();
// 用于存储前缀值的数组
int prefixArray[m];
// 调用前缀函数填充前缀数组
prefixSearch(patt, m, prefixArray);
loc = 0; // 初始化位置索引
while(i < n) {
// 检查主字符串字符是否与模式字符串字符匹配
if(orgnString[i] == patt[j]) {
// 增加 i 和 j
i++;
j++;
}
// 如果 j 和 m 相等，则找到模式
if(j == m) {
// 存储图案的位置
locArray[loc] = i-j;
loc++; // 增加位置索引
// 将 j 更新为前一个前缀值
j = prefixArray[j-1];
// 检查 i 是否小于 n 并且当前字符不匹配
}else if(i < n && patt[j] != orgnString[i]) {
if(j != 0)
// 将 j 更新为前一个前缀值
j = prefixArray[j-1];
// if j is zero
else
i++; // increment i
}
}
}
int main() {
// 声明原文
string orgnStr = "AAAABCAEAAABCBDDAAAABC";
// 找到模式
string patrn = "AAABC";
// 用于存储图案位置的数组
int locationArray[orgnStr.size()];
// to store the number of locations
int index;
// 调用模式搜索功能
patrnSearch(orgnStr, patrn, locationArray, index);
// 循环遍历位置数组
for(int i = 0; i<index; i++) {
// 打印图案的位置
cout << "在以下位置发现图案： " <<locationArray[i] << endl;
}
}
import java.io.*;
// class to implement the KMP algorithm
public class KMPalgo {
// 查找前缀的函数
public static void prefixSearch(String pat, int m, int[] storePrefx) {
int length = 0;
// 存储前缀的数组
storePrefx[0] = 0;
int i = 1;
while (i < m) {
// 检查当前字符是否与前一个字符匹配
if (pat.charAt(i) == pat.charAt(length)) {
// 增加长度
length++;
// 将长度存储在前缀数组中
storePrefx[i] = length;
} else {
if (length != 0) {
// 更新前一个前缀的长度
length = storePrefx[length - 1];
i--;
} else
// 如果长度为 0，则将 0 存储在前缀数组中
storePrefx[i] = 0;
}
i++; // incrementing i
}
}
// 搜索模式的函数
public static int patrnSearch(String orgnString, String patt, int[] locArray) {
int n, m, i = 0, j = 0;
n = orgnString.length();
m = patt.length();
// 用于存储前缀值的数组
int[] prefixArray = new int[m]; // 为前缀数组分配内存
// 调用前缀函数填充前缀数组
prefixSearch(patt, m, prefixArray);
int loc = 0; // 初始化位置索引
while (i < n) {
// 检查主字符串字符是否与模式字符串字符匹配
if (orgnString.charAt(i) == patt.charAt(j)) {
// 增加 i 和 j
i++;
j++;
}
// 如果 j 和 m 相等，则找到模式
if (j == m) {
// 存储图案的位置
locArray[loc] = i - j;
loc++; // 增加位置索引
// 将 j 更新为前一个前缀值
j = prefixArray[j - 1];
// 检查 i 是否小于 n 并且当前字符不匹配
} else if (i < n && patt.charAt(j) != orgnString.charAt(i)) {
if (j != 0)
// 将 j 更新为前一个前缀值
j = prefixArray[j - 1];
// if j is zero
else
i++; // increment i
}
}
return loc;
}
public static void main(String[] args) throws IOException {
// 声明原文
String orgnStr = "AAAABCAEAAABCBDDAAAABC";
// 找到模式
String patrn = "AAABC";
// 用于存储图案位置的数组
int[] locationArray = new int[orgnStr.length()];
// 调用模式搜索功能
int index = patrnSearch(orgnStr, patrn, locationArray);
// 循环遍历位置数组
for (int i = 0; i < index; i++) {
// 打印图案的位置
System.out.println("在以下位置发现图案： " + locationArray[i]);
}
}
}
# 查找前缀的函数
def prefix_search(pattern, m, store_prefx):
length = 0
# 存储前缀的数组
store_prefx[0] = 0
i = 1
while i < m:
# 检查当前字符是否与前一个字符匹配
if pattern[i] == pattern[length]:
# 增加长度
length += 1
# 将长度存储在前缀数组中
store_prefx[i] = length
else:
if length != 0:
# 更新前一个前缀的长度
length = store_prefx[length - 1]
i -= 1
else:
# 如果长度为 0，则将 0 存储在前缀数组中
store_prefx[i] = 0
i += 1 # incrementing i
# 搜索模式的函数
def pattern_search(orgn_string, patt, loc_array):
n = len(orgn_string)
m = len(patt)
i = j = loc = 0
# 用于存储前缀值的数组
prefix_array = [0] * m
# 调用前缀函数填充前缀数组
prefix_search(patt, m, prefix_array)
while i < n:
# 检查主字符串字符是否与模式字符串字符匹配
if orgn_string[i] == patt[j]:
# 增加 i 和 j
i += 1
j += 1
# 如果 j 和 m 相等，则找到模式
if j == m:
# 存储图案的位置
loc_array[loc] = i - j
loc += 1 # 增加位置索引
# 将 j 更新为前一个前缀值
j = prefix_array[j - 1]
# 检查 i 是否小于 n 并且当前字符不匹配
elif i < n and patt[j] != orgn_string[i]:
if j != 0:
# 将 j 更新为前一个前缀值
j = prefix_array[j - 1]
else:
i += 1 # increment i
return loc
# main function
def main():
# 声明原文
orgn_str = "AAAABCAEAAABCBDDAAAABC"
# 找到模式
patrn = "AAABC"
# 用于存储图案位置的数组
location_array = [0] * len(orgn_str)
# 调用模式搜索功能
index = pattern_search(orgn_str, patrn, location_array)
# 循环遍历位置数组
for i in range(index):
# 打印图案的位置
print("在以下位置发现图案：", location_array[i])
# 调用 main 主函数
if __name__ == "__main__":
main()
输出
在以下位置发现图案： 1 在以下位置发现图案： 8 在以下位置发现图案： 17
