关键词：
参考技术A 假设我们要从 主字符串goodgoogle 中匹配 子字符串google朴素模式匹配算法就是 通过从主字符的头部开始 一次循环匹配的字符串的挨个字符 如果不通过 则主字符串头部位置遍历位置+1 在依次遍历子字符串的字符
匹配过程
主字符串从第一位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出d 取出g 不匹配 主字符串遍历位置+1
主字符串从第二位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第三位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第四位开始 取出d 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第五位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出g 取出g 匹配
取出l 取出l 匹配
取出e 取出e 匹配 子循环结束 匹配成功
假设主字符串 长度为 n 子字符串长度为m n>= m
最好的情况需要匹配m次 时间复杂度为 0(m)
例如 000000000001 匹配 00001 每次进入子循环之后 都要遍历到最后一次子循环才得出不匹配
需要匹配次数 (n-m+1) * m
最坏的情况需要匹配m次 时间复杂度为 0((n-m+1) * m)
KMP 算法的主要核心就是 子字符串在子循环内得出不匹配时 主字符串当前的判断位不需要回溯–也就是不可以变小 ，且子循环的判断位需要回溯 回溯位与子字符串本身是否具有重复结构有关 。 以此来规避无效的判断
时间复杂度为 O(n+m)
如果主串 S = "abcdefgab" 我们要匹配的子串 T = "abcdex" 如果用前面的朴素算法 ， 前5个字母完全相同
直到第6个字母 f 和 x 不同
步骤1
S: a b c d e f g a b
T: a b c d e x
接下来如果用朴素算法的话 那么应该是如下比较
步骤2
S: a b c d e f g a b
T: # a b c d e x
b 和 a 不匹配
步骤3
S: a b c d e f g a b
T: # # a b c d e x
a和c 不匹配
步骤4
S: a b c d e f g a b
T: # # # # a b c d e x
d和a 不匹配
步骤5
S: a b c d e f g a b
T: # # # # a b c d e x
a和e 不匹配
步骤6
S: a b c d e f g a b
T: # # # # # a b c d e x
即主串S中的第2 ，3 ， 4， 5， 6 位都与子串T的首字符不相等
对于子串T来说 如果首字符a与后面的bcdex中任意一个字符都不相等
那么对于上面的第一步来说 前五位都相等 那么 可以得到 子串首字符a 与主串的第2，3，4，5 位都不相等
即步骤2 ， 3 ，4 ，5 都是多余的 可以直接进入步骤6
如果子串的首字符串与后面的字符有相等的情况
假设S = "abcababca" T= "abcabx"
朴素算法
步骤1
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
步骤2
S: a b c a b a b c a
T: # a b c a b x
b 与 a 不匹配
步骤3
S: a b c a b a b c a
T: # # a b c a b x
c 与 a 不匹配
步骤4
S: a b c a b a b c a
T: # # # a b c a b x
a 与 a 匹配
步骤5
S: a b c a b a b c a
T: # # # # a b c a b x
b 与 b 匹配
步骤6
S: a b c a b a b c a
T: # # # # a b c a b x
a 与 c 不匹配
因为步骤1 中已经得出 前五位已经完全匹配 并且子串首字符ab 存在相同的情况 所以 步骤2，3 是多余的
直接进入步骤4 因为步骤1中已经得出 主串与子串前五位相同 同时 子串1 2 位与 子串的4 5 位相同 所以可得出
子串1 2 位 与当前主串匹配位置开始的前两位也就是主串的4 5 位匹配 所以步骤4 , 5 是多余的 可以直接进入步骤6
通过上面的两个例子我们可以发现 主串的比较位是不会回溯的 ， 而子串的比较位与子串本身结构中是否有重复相关
子串不重复 举例
S: a b c d e f g a
T: a b c d e x
子串第6位不匹配 且本身没有重复 那么下一次循环 就变成了 子串的第一位与主串的第二位比较
即子串的匹配位从6 变成了1
S: a b c d e f g a
T: # a b c d e x
子串重复 举例
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
子串在第六位发生不匹配是 前五位abcab 具有重复结构 ab 所以子串匹配位发生变化 即子串的匹配位从6 变成了 3
S: a b c a b a b c a
T: # # # a b c a b x
a 与 c 不匹配
我们可以得出 子串匹配位的值 与主串无关 只取决于当前字符串之前的串前后缀的相似度
也就是说 我们在查找字符前 ，要先对子串做一个分析 获取各个位置不匹配时 下一步子串的匹配位
前缀 ： 从头开始数 不包含最后一位
后缀 : 不是倒着数 是以和前缀相同的字符串为结尾的部分
例如 字符串 a 没有前后缀
字符串 ab 没有前后缀
字符串 aba 没有前后缀
字符串 abab 前后缀 ab
字符串 ababa 前后缀 可以是 a 可以是 aba 我们取长度最长的 即 aba
第一位时 next值固定为0
其他情况 取其公共最长前后缀的长度+1 没有则为1
因为一共子串有8位 所以在子循环内一共需要获取 8次前后缀
这里我们定义一个next数组 长度为8 里面的元素分别对应子串各个子循环内的 前后缀长度
第1位不匹配时 获取字符串为a 没有前字符串 没有前后缀 那么next[1] = 0
第2位不匹配时 获取字符串为ab 有前字符串a 没有前后缀 那么next[2] = 1
第3位不匹配时 获取字符串为aba 有前字符串ab 没有前后缀 那么next[3] = 1
第4位不匹配时 获取字符串为abab 有前字符串aba 前后缀 a 那么next[4] = 2
第5位不匹配时 获取字符串为ababa 有前字符串abab 前后缀 ab 那么next[5] = 3
第6位不匹配时 获取字符串为ababaa 有前字符串ababa 前后缀 aba 那么next[6] = 4
第7位不匹配时 获取字符串为ababaab 有前字符串ababaa 前后缀 a 那么next[7] = 2
第8位不匹配时 获取字符串为ababaabc 有前字符串ababaab 前后缀 ab 那么next[8] = 3
next数组为[ 0, 1 , 1 ,2 , 3, 4 ,2, 3 ]
后来有人发现 KMP还是有缺陷的 比如 当子串 T = "aaaaax"
在5位发生不匹配 此时 next[5] = 4 接着就是 子串中的第四位a与 主串当前位置字符比较
因为子串第五位等于子串第四位相同 所以可以得出该步骤也不匹配 此时 next[4] = 3
依然不匹配 直到next[1] = 0
我们可以发现由于T串中的 2 3 4 5 位置都与首位a 相等 中间的过程都是多余的
那么可以用首位的next[1] 的值 去替代与它相等的字符后续的next[x]的值
(王道408考研数据结构)第四章串-第二节：串的模式匹配算法（朴素和kmp）
...经常使用的搜索功能所反映的就是串的匹配问题，相应的算法也是层出不穷，各有优缺点，本节主要涉及两种算法：朴素算法和KMP算法在讲解之前，有几个术语需要掌握主串模式串子串字符串模式匹配：在主串中找到与模式串相... 查看详情
字符串模式匹配kmp算法
...式串在一个较长的字符串中出现的位置。朴素的模式匹配算法很直观的可以写出下面的代码，来找出模式串在一个长字符串中出现的位置。/*朴素的模式匹配算法功能：字符串的模式匹配参数：s：目标串p：模式串pos：开发匹配... 查看详情
串的匹配：朴素匹配&kmp算法
引言字符串的模式匹配是一种经常使用的操作。模式匹配(patternmatching)，简单讲就是在文本(text，或者说母串str)中寻找一给定的模式(pattern)。通常文本都非常大。而模式则比較短小。典型的样例如文本编辑和DNA分析。在进行文本... 查看详情
串的模式匹配算法之kmp(代码片段)
title:串的模式匹配算法之kmptags:数据结构与算法之美author:辰砂1.引言首先我们需要了解串的模式算法目的：确定主串中所含子串第一次出现的位置（定位）；常见的算法种类：BF算法（又称古典的、经典的、朴素的、穷举的），KM... 查看详情
字符串匹配：kmp算法
一、原理： KMP算法是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。朴素算法（即暴力循环）的效率太差... 查看详情
4.2串的模式匹配算法(代码片段)
<?phpheader("content-type:text/html;charset=utf-8");classLinear_string/***串模式匹配算法**包括*1.串的初始化__contruct()*2.朴素的模式匹配算法index()*3.KMP模式匹配算法*4.改进的KMP模式匹配算法*/private$string;private$length;//构造函数p 查看详情
kmp算法详解
参考技术AKMP模式匹配算法KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模... 查看详情
kmp算法详解及其java实现(代码片段)
KMP算法，又称作“看猫片”算法（误），是一种改进的字符串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作，其核心思想在于：当一趟匹配过程中出现字符不匹配时，不需要回溯主串的指针，而是利用已经... 查看详情
kmp算法模式串匹配
转载：字符串匹配 kmp算法 查看详情
21天学习挑战赛kmp模式匹配算法(代码片段)
...一步有一份的欢喜。目录【21天学习挑战赛】KMP模式匹配算法✌我为什么参与挑战赛🍉模式匹配算法？💬KMP模式匹配算法的定义✨KMP模式匹配算法的优劣优势劣势🍵KMP模式匹配算法的步骤✍️算法实现【21天学习... 查看详情
kmp算法
KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。但是相较于其他模式匹配算法，该算法晦涩难懂，... 查看详情
kmp算法
KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。但是相较于其他模式匹配算法，该算法晦涩难懂，... 查看详情
kmp模板
KMP算法是高速字符串匹配算法，朴素的暴力算法的时间复杂度为O（n*m）。而KMP通过对模式串进行对应的处理，可以达到O（m+n）的速度。我们知道在字符串匹配的时候最消耗时间的就是当匹配到第i个位置发现不匹配时。下一... 查看详情
kmp子串查找算法
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法，由他们的名字首字母组成）。KMP算法的关键是利用已经部分匹配的信息，尽量减少... 查看详情
kmp算法(代码片段)
串的朴素模式匹配算法什么是字串匹配：在主串中找到与模式串相同的字串并返回其位置，如主串google、模式串gle，则结果为3算法思路：相当于拿着模式串和主串对齐，对比其第一个字符。不相等则模式串往... 查看详情
模式匹配----kmp算法(代码片段)
...为她打着伞、在上篇中，我们讲到了BF暴力模式匹配算法。下面我们将讲述BF算法的优化版本算法KMP算法。🎃KMP定义我们知道BF算法效率低的原因就是要回溯，即在匹配失败后，子串回溯到0，主串回溯到本趟匹... 查看详情
模式匹配----kmp算法(代码片段)
...为她打着伞、在上篇中，我们讲到了BF暴力模式匹配算法。下面我们将讲述BF算法的优化版本算法KMP算法。🎃KMP定义我们知道BF算法效率低的原因就是要回溯，即在匹配失败后，子串回溯到0，主串回溯到本趟匹... 查看详情
kmp算法
转自http://blog.csdn.net/joylnwang/article/details/6778316/KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。但是... 查看详情