Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2121618
  • 博文数量: 288
  • 博客积分: 10594
  • 博客等级: 上将
  • 技术积分: 3469
  • 用 户 组: 普通用户
  • 注册时间: 2006-10-27 19:27
文章分类

全部博文(288)

文章存档

2012年(4)

2011年(30)

2010年(40)

2009年(32)

2008年(71)

2007年(79)

2006年(32)

分类: C/C++

2007-11-22 22:22:07

一种改进的字符串匹配算法,由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
此时,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           ‘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
#include
#include
using namespace std;

inline void NEXT(const string& T,vector& next)
{
    //按模式串生成vector,next(T.size())   
    next[0]=-1;            
    for(int i=1;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 next(T.size());
    NEXT(T,next);
    string::size_type index,count=0;   
    for(index=0;index         int pos=0;
        string::size_type iter=index;
        while(pos             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<
  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 = 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
阅读(1610) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~