kmp算法的改进

❶ 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，继续进行比较。

❷ 什么情况下，KMP算法的性能会退化为朴素匹配算法

（1）未改进的模式匹配算法的时间复杂度为O（nm），但在一般情况下，其实际的执行时间接近O（n＋m），因此至今仍被采用。

（2）KMP算法仅当模式与主串之间存在许多“部分”匹配的情况下才显得比未改进的模式匹配快。

（2）KMP算法的最大特点是指示主串的指针不需要回溯，在整个匹配过程中，对主串仅需要从头至尾扫描一遍，这对处理存储在外存上的大文件是非常有效的。

(2)kmp算法的改进扩展阅读：

KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时，主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退,从而可以大大提高效率。

如果模式P与目标T(或其子串)存在某种程度的相似,则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换来组成。

❸ 关于KMP匹配中next[i]数组的改进算法问题

{ //求KMP算法中的next函数值，并存入数组next[] int i=1; next[1]=1.在程序中有字符串S和T，你用S[0]代表字符串的长度，但S是字符串，S

❹ 模式p=＇abcaababc ＇的KMP算法和KMP，并改进算法的匹配过程！

求子串next[j]值的算法：
void GetNext(String T, int next[])
{ int j = 1, k = 0;
next[1] = 0;
while(j < len(T)){

if( k == 0 || T[j]==T[k])
{j++; k++; next[j]=k; }
else k = next[k];
}
}
KMP 算法的自然语言描述
设s为主串，t为模式串，设i为主串s当前比较字符的下标，j为模式串t当前比较字符的下标，令i和j的初值为pos和1。当si = tj时，i和j分别增1再继续比较；否则 i不变，j改变为next[j]值（即模式串右滑）后再继续比较。依次类推，直到出现下列两种情况之一：
一是 j退回到某个j=next[j]值时有si = tj ，则 i和j分别增1后再继续比较；
二是j退回到j=0时，令主串和子串的下标各增1，随后比较si和t1 。这样的循环过程一直进行到变量大于等于s的长度或变量j大于等于t的长度为止。
int KMPIndex(String S, int start,String T, int next[ ])
{
int i = start, j=1;

while ( i <= S[0] && j< T[0]) {
//不失配则继续比较后续字符
if (j == 0 || S [i] = = T[j] ) {i++; j++ }
//特点：S的i指针不回溯，而且从T的k位置开始匹配
else j=next[j];
}

if (j >= T[0]) return ( i-T(0) );
else return -1;
}

❺ kmp算法的改进中，改进算法总是运行不出来！！求帮助。错误显示First-chance exception in zxl.exe: 0xC000

请输入长串S:1111
请输入子串T:1
匹配成功，初始匹配成功的位置为第：1个字符
匹配次数为：1
请按任意键继续. . .

我运行OK的啊

❻ kmp算法难吗是什么级别

KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练，但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂，很多正规的书本把概念一摆出直接劝退无数人。这篇文章将尽量以最详细的方式配图介绍KMP算法及其改进。文章的开始我先对KMP算法的三位创始人Knuth,Morris,Pratt致敬，懂得这个算法的流程后你真的不得不佩服他们的聪明才智。

❼ kmp算法的介绍

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。

❽ kmp算法详解

KMP模式匹配算法
KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。
求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数[3]。
include "string. h"

#include<assert. h>

int KMPStrMatching(String T, String P, int. N, int startIndex)

{int lastIndex=T.strlen() -P.strlen();

if((1 astIndex- startIndex)<0)//若 startIndex过大,则无法匹配成功

return (-1);//指向P内部字符的游标

int i;//指向T内部字符的游标

int j=0;//指向P内部字符的游标

for(i= startIndex; i <T.strlen(); i++)

{while(P[j]!=T[i]&& j>0)

j=N[j-1];

if(P[j]==T[i])

j++;

if(j ==P.strlen())

return(1-j+1);//匹配成功,返回该T子串的开始位置

}

return (-1);

}

❾ 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算法的基本思想

主串：a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b，下文中我们称作T
模式串：a
b
a
c
a
b，下文中我们称作W
在暴力字符串匹配过程中，我们会从T[0]
跟
W[0]
匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从T[1]
跟
W[0]匹配，循环进行，直到主串结束，或者出现匹配的情况。这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率。
然而，在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。
在第一次匹配过程中
T:
a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：
T:
a
b
a
c
aab
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
然而，有些同学可能会问了，每次都要计算最长的相同的前缀会不会反而浪费了时间，对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间是常数时间。比如：
j012345W[j]abacabF(j)001012当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函数的计算算法。