KPM算法解决字符串匹配问题
- 什么是KPM算法
- 步骤
- Ⅰ根据《最大长度表》部分匹配表（next）
- 寻找最长前缀后缀
- Ⅱ 根据 部分匹配表 进行匹配
- 代码实现
什么是KPM算法
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间。
- KPM的使用场景：模式串在文本串是否出现过，如果出现过，最早出现的位置
步骤
Ⅰ根据《最大长度表》部分匹配表（next）
对于
P = p0 p1 ...pj-1 pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。
举个例子，如果给定的模式串为“abab”，那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示：
比如对于字符串aba来说，它有长度为1的相同前缀后缀a；而对于字符串abab来说，它有长度为2的相同前缀后缀ab（相同前缀后缀的长度为k + 1，k + 1 = 2）。
结论：最大前缀后缀元素长度所得到的数组就是我们所需要的 “部分匹配表”
寻找最长前缀后缀
- 如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：
Ⅱ 根据 部分匹配表 进行匹配
匹配失配，
j = next [j]，模式串向右移动的位数为：j - next[j]。换言之，当模式串的后缀pj-k pj-k+1, ..., pj-1跟文本串si-k si-k+1, ..., si-1匹配成功，但pj跟si匹配失败时，因为next[j] = k，相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀，即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令j = next[j]，从而让模式串右移j - next[j]位，使得模式串的前缀p0 p1, ..., pk-1对应着文本串si-k si-k+1, ..., si-1，而后让pk跟si继续匹配。如下图所示：
KMP的next数组相当于告诉我们：
当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在j处的字符跟文本串在i处的字符匹配失配时，下一步用next [j]处的字符继续跟文本串i 处的字符匹配，相当于模式串向右移动j - next[j]位。
代码实现
字符串匹配问题：
有一个字符串 str1=““上海自来水来自海上””，和一个子串 str2=“自来水”。
现在要判断str1是否含有str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
static void Main(string[] args)
{string str1 = "上海自来水来自海上";string str2 = "自来水";// 得出 部分匹配表int[] next = KPMNext(str2);// 根据 得出的 部分匹配表的 next 数组进行匹配，int index = KPMSearch(str1, str2, next);Console.WriteLine(index);
}/// <summary>
/// 获取一个字符串的部分匹配值表
/// </summary>
/// <param name="dest"></param>
/// <returns></returns>
static int[] KPMNext(string dest)
{// 初始化 数组大小int[] next = new int[dest.Length];// 字符串长度为1，部分匹配值就为0next[0] = 0;for (int i = 1, j = 0; i < dest.Length; i++){while (j > 0 && dest[i] != dest[j]){j = next[j - 1];}if (dest[i] == dest[j]){j++;}next[i] = j;}return next;
}/// <summary>
/// kmp搜索
/// </summary>
/// <param name="str1">源字符串</param>
/// <param name="str2">子字符串</param>
/// <param name="next">部分匹配表</param>
/// <returns></returns>
static int KPMSearch(string str1, string str2, int[] next)
{for (int i = 0, j = 0; i < str1.Length; i++){while (j > 0 && str1[i] != str2[j]){j = next[j - 1];}if (str1[i] == str2[j]){j++;}if (j == str2.Length){return i - j + 1;}}return -1;
}
