大家好,今天小编来为大家解答以下的问题，关于高效字符串匹配算法：KMP算法解析与应用，这个很多人还不知道，现在让我们一起来看看吧！
1.引言
首先我们要了解字符串的模式算法的目的：确定主字符串中包含的子字符串第一次出现的位置（定位）；常见的算法类型：
BF算法（又称经典、经典、简单、穷举）、KMP算法（特点：快速）。网上有很多帖子，博客都写得很好。这篇文章也是我自己的一个总结。
2.BF算法
BF算法设计思路：
将主字符串的第pos-th 字符与模式的第一个字符进行比较
如果相等，则继续一一比较后续字符；
如果不是，则从主字符串的下一个字符开始，再次将其与模式的第一个字符进行比较。
直到主字符串的连续子字符串字符序列等于模式。
返回值是S中与T匹配的子序列的第一个字符的序号，即匹配成功。
否则，匹配失败并返回0值。
1.举例：
假设现在我们面临这样一个问题：有一个文本字符串S和一个模式字符串P。现在我们想找到P在S中的位置。如何找到呢？
如果用暴力匹配的思想，假设文本串S匹配到i位置，模式串P匹配到j位置，那么有：
如果当前字符匹配成功（即S[i]==P[j]），则i++、j++继续匹配下一个字符；
如果存在不匹配（即S[i]！=P[j]），则令i=i - (j - 1)（表示主串的位置返回到当前下一个位置），j=0。相当于每次匹配失败，i就返回，j设置为0。
公共静态int bfMatch(char[] s, char[] p) {
int sLen=s.length;
int pLen=p.length;
整数i=0;
整数j=0;
while (i sLen j pLen) {
如果(s[i]==p[j]) {
//如果当前字符匹配成功（即S[i]==P[j]），则i++,j++
我++；
j++;
} 别的{
// 如果存在不匹配（即S[i]！=P[j]），则令i=i - (j - 1), j=0
//i - (j - 1) 表示主字符串的位置返回到当前下一个位置。
i=i - j + 1；
j=0；
}
}
//如果匹配成功，则返回模式串p在文本串s中的位置，否则返回-1
如果(j==pLen) {
返回i - j；
} 别的{
返回-1；
}
}
公共静态无效主（字符串[] args）{
字符串s="BBC ABCDAB ABCDABCDABDE";
字符串p="ABCDABD";
System.out.println(bfMatch(s.toCharArray(),p.toCharArray()));
}
2.时间复杂度说明：
如果n是主字符串的长度，m是子字符串的长度，那么最坏的情况是
主串的前n-m个位置部分匹配子串的最后一位，即n-m个位中的每一个都被比较m次。
最后m 位也各比较一次。
总次数为：(n-m)m+m=(n-m+1)m
如果米
网上有一个很好的例子，我引用一下：
例如，如果给定文本字符串S“BBC ABCDAB ABCDABCDABDE”和模式字符串P“ABCDABD”，现在需要使用模式字符串P来匹配文本字符串S，整个过程如下：
1.S[0]为B，P[0]为A，不匹配，执行指令：“如果不匹配（即S[i]！=P[j]），令i=i - (j - 1), j=0", S[1] 匹配P[0]，相当于模式串右移一位（i=1, j=0）
这里插入图片描述2. S[1]和P[0]仍然不匹配，继续执行指令：“如果不匹配（即S[i]！=P[j]），令i=i - (j - 1), j=0", S[2] 匹配P[0] (i=2, j=0)，因此模式串不断向右移动一位（连续执行“令i=我- (j - 1), j=0", i 从2 变为4, j 始终为0)
这里插入图片描述3.直到S[4]和P[0]匹配成功（i=4,j=0），此时根据上面暴力匹配算法的思想，第一条指令是执行：“如果如果当前字符匹配成功（即S[i]==P[j]），则i++,j++”，可以得出S[i]为S[5],P[j]是P[1]，即下一个S[5]匹配P[1]（i=5,j=1）
这里插入图片描述4、S[5]和P[1]匹配成功，继续执行第一条指令：“如果当前字符匹配成功（即S[i]==P[j]），则i++，j++ ”，得到S[6] 匹配P[2] (i=6, j=2)，然后像这样继续
在此插入图片说明5。直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行指令：“如果有不匹配（即S [i]!=P[j])，令i=i - (j - 1), j=0"，相当于将S[5] 与P[0] 匹配(i=5, j=0)
这里插入图片描述6. 此时我们可以看到，如果按照暴力匹配算法的思路，虽然前面的文本串和模式串分别匹配到了S[9]和P[5] ，因为S[10]和P[6]不匹配，所以文本字符串追溯到S[5]，模式字符串追溯到P[0]，所以S[5]匹配P[0] 。
在此插入图片描述，S[5] 肯定与P[0] 不匹配。为什么？因为在前面的第4步匹配中，我们已经知道S[5]=P[1]=B，并且P[0]=A，即P[1] !=P[0]，所以S[ 5]一定不等于P[0]，所以回顾过去必然会导致不匹配。有没有一种算法可以让i 移动j 而无需返回？
3.KMP算法（主串指针不回溯）
算法思路：利用部分匹配结果来加快模式串的滑动速度？并且主串S的指针i不需要回溯！可以加速到O(n+m)！
算法步骤：
下面直接给出KMP的算法流程：
假设现在文本字符串S 匹配位置i，模式字符串P 匹配位置j
如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），则让i++、j++继续匹配下一个字符；
如果j !=-1，且当前字符匹配失败（即S[i] !=P[j]），则保持i不变，j=next[j]。这意味着当存在不匹配时，模式串P 相对于文本串S 向右移动j - next [j] 位。
也就是说，当匹配失败时，模式串向右移动的位数为：不匹配字符的位置- 不匹配字符对应的下一个值（下一个数组的解决方法将在后面详细解释）如下3.3.3节），即移动的实际位数为：j - next[j]，且该值大于等于1。
很快，你也会意识到next数组每个值的含义：它代表当前字符之前的字符串中相同前缀和后缀的长度。例如，如果next[j]=k，则表示j之前的字符串具有相同的前缀和后缀，最大长度为k。
这也意味着，当某个字符不匹配时，该字符对应的下一个值会告诉你下一步匹配时模式串应该跳转到哪里（跳转到next[j]的位置）。如果next [j] 等于0 或-1，则跳转到模式字符串的开头字符。如果next[j]=k且k=0，则表示下一个匹配跳转到j之前的一个字符，而不是跳转到开头。具体来说，k 个字符被跳过。
公共静态int kmpMatch(char[] s, char[] p) {
int sLen=s.length;
int pLen=p.length;
整数i=0;
整数j=0;
while (i sLen j pLen) {
如果(s[i]==p[j]) {
//如果当前字符匹配成功（即S[i]==P[j]），则i++,j++
我++；
j++;
} 别的{
j=下一个[j];
}
}
//如果匹配成功，则返回模式串p在文本串s中的位置，否则返回-1
如果(j==pLen) {
返回i - j；
} 别的{
返回-1；
}
为此，定义next[j]函数，该函数表示当模式中的第j个字符与主字符串中的相应字符“不匹配”时，需要将该字符在模式中的位置与再次主字符串中的字符。
1.如何求next()?
1.寻找前缀后缀最长公共元素长度
例如字符串‘a’的前缀为空，后缀也为空，所以前缀和后缀表示不包含当前字符串。字符串‘ab’的前缀是a，后缀是b。
定义：对于P=p0 p1 .pj-1 pj，找出模式串P 中长度最大且相等的前缀和后缀。若有p0 p1 .pk-1 pk=pj- k pj- k+1.pj-1 pj，则包含pj的模式串具有相同的前缀和后缀，最大长度为k+1。
例如：
j1234567891011121314151617 模式字符串abcaabcabcaaabdab 前缀和后缀的最长公共元素00011231234562012
2.求next数组
next 数组考虑除当前字符之外的最长公共前缀和后缀，因此之后每个前缀和后缀的公共元素的最大长度为ob沾染通过步骤，只要做一个变形即可：将步骤得到的值右移一位，然后将初始值赋值为-1，如下表所示：
此处插入图片描述j1234567891011121314151617 模式字符串abcaabcabcaaabdabnext[j]01112231123456212
3.如何求next函数值
next[1]=0;表示主字符串从下一个字符si+1开始再次匹配模式字符串。我=我+1； j=1；
假设next[j]=k，则next[j+1]=?
若pk=pj，则有“p1.pk-1pk”=“pj-k+1.pj-1pj”，若
不匹配发生在j+1 处，这意味着next[j+1]=k+1=next[j]+1。
如果pkpj，则寻找下一个值的问题可以视为模式匹配问题
问题，整个模式串既是主串又是子串。
在此插入图片说明。如果pk’=pj，则“p1…pk’”=“pj-k’+1…pj”，
下一个[j+1]=k’+1=下一个[k]+1=下一个[下一个[j]]+1。
如果pk”=pj，则“p1…pk”=”pj-k”+1…pj”，
下一个[j+1]=k”+1=下一个[k’]+1=下一个[下一个[k]]+1。
下一个[j+1]=1。
4.总结
核心点是：之前的bf算法需要i回溯，导致时间复杂度为O(m*n)。现在kmp算法的核心是i不回溯，j的值是不确定的。根据字符串规则，如果主字符串前面成功匹配的字符串的前缀和后缀相等，则不需要匹配。时间复杂度为O(m + n)
引用博客示例：
1. 初次匹配时
P[0] 未能匹配S[0]
所以执行“如果j !=-1，且当前字符匹配失败（即S[i] !=P[j]），则让i保持不变，j=next[j]”，所以j=-1，所以而是执行“如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），则让i++,j++”，得到i=1, j=0，即，P[0]继续匹配S[1]。
P[0]和S[1]再次不匹配，j再次等于-1，i和j继续增加，因此P[0]与S[2]匹配。
P[0]和S[2]不匹配后，P[0]再次匹配S[3]。
P[0]和S[3]再次不匹配，直到P[0]和S[4]匹配成功，然后开始执行这条指令的后半部分：“如果j=-1，或者当前字符匹配成功（即S[i]==P[j]), 设i++, j++”。
在此插入图片说明2。 P[1]和S[5]匹配成功，P[2]和S[6]也匹配成功，……，直到匹配到P[6]处的字符D。匹配（即S[10] !=P[6]）。由于P[6]处的D对应的下一个值为2，因此下一步是使用P[2]处的字符C继续与S[10]匹配。相当于向右移动：j - next[j]=6 - 2=4 位。
此处插入图片描述3. 右移4 位后，P[2]处的C 再次不匹配。由于C对应的下一个值为0，所以下一步使用P[0]处的字符继续与S[10]匹配，相当于向右移动：j - next[j]=2 - 0=2 位。
此处插入图片描述4. 移动两位后，A 与空格不匹配，模式串向后移动1 位。
在此插入图片说明5。 P[6]处的D又不匹配了，因为P[6]对应的下一个值为2，所以下一步就是用P[2]继续匹配文本串，相当于模式串去正确的。移动j - next[j]=6 - 2=4 位。
此处插入图片描述6. 匹配成功，流程结束。
这里插入图片来描述匹配过程完全一样。也从侧面证明了next数组确实只需要将每个最大前缀和后缀的公共元素的长度值向右移动一个位置，并将初始值赋为-1即可。
代码如下：
void get_next(SString T, int next[])
{
我=1;下一个[1]=0; j=0；
而（我
好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！
【高效字符串匹配算法：KMP算法解析与应用】相关文章：
用户评论
这个标题感觉专业 banget deh!
有6位网友表示赞同！
想学一下字符匹配算法，KMP好像是个不错的选择。
有19位网友表示赞同！
看标题就觉得有点复杂，需要好好研究一下才行。
有16位网友表示赞同！
串和模式匹配？听起来挺有意思的，希望文章能讲解得详细点
有19位网友表示赞同！
我一直对算法很感兴趣，KMP算法我也听说过，希望能从这篇文章中了解更多。
有14位网友表示赞同！
感觉编程需要用到这种串模式匹配算法吧？
有20位网友表示赞同！
KMP算法的名字听着就高大上，是不是很难学啊？
有16位网友表示赞同！
文章能讲解到具体的例子吗？这样更容易理解。
有19位网友表示赞同！
学习算法的过程总是充满了挑战和乐趣！
有13位网友表示赞同！
希望这篇文章能让我对KMP算法有更深入的理解!
有19位网友表示赞同！
码农必备的技能，看来要好好研究一下才行。
有12位网友表示赞同！
之前没听说过KMP，这篇文章应该是我了解它的一个机会！
有9位网友表示赞同！
算法学习真是不断进步的过程，期待这篇论文让我学到更多。
有17位网友表示赞同！
编程和数据分析经常用到这类匹配算法吧？
有6位网友表示赞同！
感觉 KMP 算法应该很实用的啊。
有14位网友表示赞同！
喜欢阅读关于算法的文章，可以扩展我的知识面！
有13位网友表示赞同！
这篇文章能否讲解一下KMP算法的应用场景呢？
有15位网友表示赞同！
学习新东西总是心动的，期待这篇关于KMP算法的文章能给我启发！
有19位网友表示赞同！
计算机科学的精彩之处在于这些优秀的算法!
有13位网友表示赞同！