改进的kmp算法

❶ kmp算法的优化

KMP算法是可以被进一步优化的。
我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 但是，如果此时发现p(i) == p(k），那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 优化的next[i] -1 0 0 0 -1 1 0 0 3 0 （1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
补充一个next[]生成代码： voidgetNext(constchar*pattern,intnext[]){next[0]=-1;intk=-1,j=0;while(pattern[j]!=''){while(k!=-1&&pattern[k]!=pattern[j])k=next[k];++j;++k;if(pattern[k]==pattern[j])next[j]=next[k];elsenext[j]=k;}} PROGRAMImpl_KMP;USESCRT;CONSTMAX_STRLEN=255;VARnext:array[1..MAX_STRLEN]ofinteger;str_s,str_t:string;int_i:integer;Procereget_next(t:string);Varj,k:integer;Beginj:=1;k:=0;whilej<Length(t)dobeginif(k=0)or(t[j]=t[k])thenbeginj:=j+1;k:=k+1;next[j]:=k;endelsek:=next[k];end;End;Functionindex(s:string;t:string):integer;Vari,j:integer;Beginget_next(t);index:=0;i:=1;j:=1;while(i<=Length(s))and(j<=Length(t))dobeginif(j=0)or(s[i]=t[j])thenbegini:=i+1;j:=j+1;endelsej:=next[j];ifj>Length(t)thenindex:=i-Length(t);end;End;BEGINClrScr;{清屏，可不要}Write('s=');Readln(str_s);Write('t=');Readln(str_t);int_i:=index(str_s,str_t);ifint_i<>0thenbeginWriteln('Found''',str_t,'''in''',str_s,'''at',int_i,'.');endelseWriteln('Cannotfind''',str_t,'''in',str_s,'''.');END.index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0

❷ 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算法的时间复杂度为什么是O(n)

主串T，比较串P，
由于KMP算法的思想是主串不回溯的简化算法，执行的时候呢在串比较的扫描里面要么执行POST和POSP，要么执行NEXT[]数组的右移，然后比较，所以字符比较最多就是为O（LenthT）,即不会超过O（n）
其实KMP看起来很吓人，但是你抓住它的思想“主串不回溯”就很简单了.

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

❹ 字符串匹配算法的基本思想是什么

这个用到了正规表达式对字符串的匹配.程序如下,是javascript的.
<script language="javascript">
function check(obj)
{var str=/^[0-9]{4}-[0-9]{7}$/ig;
if(str.test(obj))
alert("this is your number");
else
alert("write again");}
</script>
<form name="form1">
<input type="text" name="mytext" size="12">
<input type="button" value="click" onclick="check

(form1.mytext.value)">
</form>
要求输入的是标准电话号码.看不懂问我.呵呵.

❺ 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函数的计算算法。

❻ 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与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。
完全掌握KMP算法思想
学过数据结构的人，都对KMP算法印象颇深。

❽ 关于KMP算法的说明有什么

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

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

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

❾ 什么是KMP算法

KMP就是串匹配算法
运用自动机原理
比如说
我们在S中找P
设P＝{ababbaaba}
我们将P对自己匹配
下面是求的过程:{依次记下匹配失败的那一位}
[2]ababbaaba
......ababbaaba[1]
[3]ababbaaba
........ababbaaba[1]
[4]ababbaaba
........ababbaaba[2]
[5]ababbaaba
........ababbaaba[3]
[6]ababbaaba
..............ababbaaba[1]
[7]ababbaaba
..............ababbaaba[2]
[8]ababbaaba
.................ababbaaba[2]
[9]ababbaaba
.................ababbaaba[3]
得到Next数组‘0,1,1,2,3,1,2,2,3’
主过程：
[1]i:=1 j:=1
[2]若(j>m)或(i>n)转[4]否则转[3]
[3]若j=0或a[i]=b[j]则【inc(i)inc(j)转[2]】否则【j:=next[j]转2】
[4]若j>m则return(i-m)否则return -1;
若返回－1表示失败，否则表示在i-m处成功
若还不懂mail:[email protected]

参考一下这里吧:

http://www.chinaaspx.com/archive/delphi/4733.htm