串行串匹配算法

KMP算法

    KMP算法的关键是根据给定的模式串W[1,m],定义一个next函数。next函数包含了模式串本身局部匹配的信息。next函数的定义如下：

       

    KMP算法的基本思想是：假设在模式匹配的进程中，执行T[i]和W[j]的匹配检查。若T[i]=W[j]，则继续检查T[i+1]和 W[j+1]是否匹配。若T[i]<>W[j]，则分成两种情况：若j=1，则模式串右移一位，检查T[i+1]和W[1]是否匹配；若1& lt;j<=m，则模式串右移j-next(j)位，检查T[i]和W[next(j)]是否匹配。重复此过程直到j=m或i=n结束。

 

kmp算法

[编辑本段 ]

kmp算法-概述

　　一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。

[编辑本段 ]

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值是怎么求出来的，我教你怎么学会。
　　课本83页不是有个例子吗？就是 图4.6
　　你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的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="abaabcacabaabcacabaabcacabaabcacabaabcac";
　　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;
　　Procedure 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[i] = 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