印象算法
1. KMP是什么意思
一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ,匹配时间为Θ(n),只用到辅助函数π[1,m],它是在Θ(m)时间内,根据模式预先计算出来的。数组π使得我们可以按需要,“现场”有效的计算(在平摊意义上来说)变迁函数δ。粗略地说,对任意状态q=0,1,…,m和任意字符a∈Σ,π[q]的值包含了与a无关但在计算δ(q,a)时需要的信息。由于数组π只有m个元素,而δ有Θ(m∣Σ∣)个值,所以通过预先计算π而不是δ,使得时间减少了一个Σ因子。
2. 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,继续进行比较。
3. KMP是什么意思
kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。
完全掌握KMP算法思想
学过数据结构的人,都对KMP算法印象颇深。
4. 与操作系统有关的一些经典算法
哦 ,kmp算法就是一种经典算法.KMP算法
一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。
完全掌握KMP算法思想
学过数据结构的人,都对KMP算法印象颇深。尤其是新手,更是难以理解其涵义,搞得一头雾水。今天我们就来面对它,不将它彻底搞懂,誓不罢休。
如今,大伙基本上都用严蔚敏老师的书,那我就以此来讲解KMP算法。(小弟正在备战考研,为了节省时间,很多课本上的话我都在此省略了,以后一定补上。)
严老的《数据结构》79页讲了基本的匹配方法,这是基础。
80页在讲KMP算法的开始先举了个例子,让我们对KMP的基本思想有了最初的认识。目的在于指出“由此,在整个匹配的过程中,i指针没有回溯,”。
我们继续往下看:
现在讨论一般情况。
假设 主串:s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 :p: ‘p(1) p(2) p(3)…..p(m)’
现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后,主串第i个字符与模式串的第k(k<j)个字符继续比较
此时,s(i)≠p(j), 有
主串: S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串: P(1) ……. p(j-1) p(j)
由此,我们得到关系式
‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’
由于s(i)≠p(j),接下来s(i)将与p(k)继续比较,则模式串中的前(k-1)个字符的子串必须满足下列关系式,并且不可能存在 k’>k 满足下列关系式:(k<j),
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’
即:
主串: S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比较)
匹配串: P(1) p(2) …… p(k-1) p(k)
现在我们把前面总结的关系综合一下
有:
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比较)
P(1) p(2) ……. p(k-1) p(k)
由上,我们得到关系:
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’
接下来看“反之,若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段,如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)
K 是和next有关系的,不过在最初看的时候,你不要太追究k到底是多少,至于next值是怎么求出来的,我教你怎么学会。
你照着源程序,看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。
然后找几道练习题好好练练,一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了,再回去看它是怎么推出来的,如果还看不懂,就继续做练习,做完练习再看。相信自己!!!
附:
KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T!=T[j+1]&& j>=0 )
j=next[j] ; //递推计算
if(T==T[j+1])next=j+1;
else next=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空,
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
补上个Pascal的KMP算法源码
PROGRAM Impl_KMP;
USES
CRT;
CONST
MAX_STRLEN = 255;
VAR
next : array [ 1 .. MAX_STRLEN ] of integer;
str_s, str_t : string;
int_i : integer;
Procere get_nexst( t : string );
Var
j, k : integer;
Begin
j := 1; k := 0;
while j < Length(t) do
begin
if ( k = 0 ) or ( t[j] = t[k] ) then
begin
j := j + 1; k := k + 1;
next[j] := k;
end
else k := next[k];
end;
End;
Function index( s : string; t : string ) : integer;
Var
i, j : integer;
Begin
get_next(t);
index := 0;
i := 1; j := 1;
while ( i <= Length(s) ) and ( j <= Length(t) ) do
begin
if ( j = 0 ) or ( s = t[j] ) then
begin
i := i + 1; j := j + 1;
end
else j := next[j];
if j > Length(t) then index := i - Length(t);
end;
End;
BEGIN
ClrScr;
Write(s = );
Readln(str_s);
Write(t = );
Readln(str_t);
int_i := index( str_s, str_t );
if int_i <> 0 then
begin
Writeln( Found , str_t, in , str_s, at , int_i, . );
end
else
Writeln( Cannot find , str_t, in , str_s, . );
END.
index函数用于模式匹配,t是模式串,s是原串。返回模式串的位置,找不到则返回0
5. 什么是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