本文目录
- 关于KMP算法的说明有什么
- KMP算法
- 什么情况下，KMP算法的性能会退化为朴素匹配算法
- 什么是KMP算法
- KMP算法的主要特点是什么
- KMP模式匹配算法是什么
- kmp算法的介绍
- kmp算法的基本思想
- kmp算法什么意思
关于KMP算法的说明有什么
（1）未改进的模式匹配算法的时间复杂度为O（nm），但在一般情况下，其实际的执行时间接近O（n＋m），因此至今仍被采用。
（2）KMP算法仅当模式与主串之间存在许多“部分”匹配的情况下才显得比未改进的模式匹配快。
（2）KMP算法的最大特点是指示主串的指针不需要回溯，在整个匹配过程中，对主串仅需要从头至尾扫描一遍，这对处理存储在外存上的大文件是非常有效的。
KMP算法
算法3.5——KMP算法 1. 在串S和串T中分别设比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如果S[i]=T[j]，则继续比较S和T的下一个字符；否则 2.2 将j向右滑动到next[j]位置，即j=next[j]； 2.3 如果j=0，则将i和j分别加1，准备下一趟比较； 3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；void GetNext(char T[ ], int next[ ]){ next=0; j=1; k=0; while (j《T) if ((k= =0)| |(T[j]= =T[k])) { j++; k++; next[j]=k; } else k=next[k];}
什么情况下，KMP算法的性能会退化为朴素匹配算法
（1）未改进的模式匹配算法的时间复杂度为O（nm），但在一般情况下，其实际的执行时间接近O（n＋m），因此至今仍被采用。
（2）KMP算法仅当模式与主串之间存在许多“部分”匹配的情况下才显得比未改进的模式匹配快。
（2）KMP算法的最大特点是指示主串的指针不需要回溯，在整个匹配过程中，对主串仅需要从头至尾扫描一遍，这对处理存储在外存上的大文件是非常有效的。
扩展资料：
KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时，主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退,从而可以大大提高效率。
如果模式P与目标T(或其子串)存在某种程度的相似,则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换来组成。
参考资料来源：百度百科-kmp算法
什么是KMP算法
KMP就是串匹配算法 运用自动机原理 比如说 我们在S中找P 设P＝{ababbaaba} 我们将P对自己匹配 下面是求的过程:{依次记下匹配失败的那一位} ababbaaba ......ababbaaba ababbaaba ........ababbaaba ababbaaba ........ababbaaba ababbaaba ........ababbaaba ababbaaba ..............ababbaaba ababbaaba ..............ababbaaba ababbaaba .................ababbaaba ababbaaba .................ababbaaba 得到Next数组『0,1,1,2,3,1,2,2,3』 主过程： i:=1 j:=1 若(j》m)或(i》n)转否则转 若j=0或a[i]=b[j]则【inc(i)inc(j)转】否则【j:=next[j]转2】 若j》m则return(i-m)否则return -1; 若返回－1表示失败，否则表示在i-m处成功 若还不懂mail:zz_lc@163.com参考一下这里吧:http://www.chinaaspx.com/archive/delphi/4733.htm
KMP算法的主要特点是什么
kmp算法主要是减少字符串查找过程中的回退，尽可能减少不用的操作，算法复杂度是O(n+m)。思想可以使用与ac自动机。主要是先求next数组。比如当next[i] = j。也就是说0 ~ j-1所在的字符串跟i-j 到 i-1 所在的字符串是相同的。其他的原理基本一样。 你可以看看http://baike.baidu.com/view/659777.htm
KMP模式匹配算法是什么
KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。
1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。
图1改进算法的模式匹配过程示意
kmp算法的介绍
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。
kmp算法的基本思想
主串：abacaabacabacabaabb，下文中我们称作T模式串：abacab，下文中我们称作W在暴力字符串匹配过程中，我们会从T跟W匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从T跟W匹配，循环进行，直到主串结束，或者出现匹配的情况。这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率。然而，在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。在第一次匹配过程中T:abacaabacabacabaabbW:abacab在T与W出现了不匹配，而T~T是匹配的，现在T~T就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：T:abacaabacabacabaabbW:abacab然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。然而，有些同学可能会问了，每次都要计算最长的相同的前缀会不会反而浪费了时间，对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间是常数时间。比如：j 012345W[j] a bacabF(j)00 1012当W[j]与T[i]不匹配的时候，设置j=F(j-1)文献中，朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]《》W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下，朱洪的KMP算法比KMP算法更加有效。以下给出朱洪的改进KMP算法和next函数和newnext函数的计算算法。
kmp算法什么意思
KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。 在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。 对于next数组的定义如下： 1) next[j] = -1 j = 0 2) next[j] = max(k): 0《k《j P[0...k-1]=P[j-k,j-1] 3) next[j] = 0 其他 如： P a b a b a j 0 1 2 3 4 next -1 0 0 1 2 即next[j]=k》0时，表示P[0...k-1]=P[j-k,j-1] 因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]》=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。