冬天¤不回来
海风轻轻吹过我的脸庞 阳光温柔的洒在我身上 海鸥自由的飞在天空中像 快乐的徘徊在游乐场 白云在偷看彩虹的模样 海洋总为那船长指方向 海浪抚摸著沙滩的衣裳 我也每天都为他换上新装 找到方向 揭开迷茫 学着坚强 努力去闯!
posts - 20,  comments - 90,  trackbacks - 0

             KMP 匹配算法是由 "Knuth  Morris  Pratt"  提出的一种快速的模式匹配算法. ()


1.待解决的问题: 假设P为给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串,这称为模式匹配问题. (可以给出子串在T中的位置) (下文中提
到的PT分别为子串和目标串)

让我们先来看个例题:

T:   t0      t1     t2      t3 .... tm-1 ... tn-1

P:   p0      p1     p2      p3 .....pm-1          
                                               

T的最左边开始比较,使得 TK = PK  , 则匹配成功


2.解决模式匹配问题的方案:

A: 
朴素的模式匹配算法(思路简单,但不够简便时间长 有回溯) : 最简单和最直接的做法.P中的字符依次与T中的字符进行比较 遇到不相等的字符,则可将P右移一个字符,从新进行比较,直到某次匹配成功或者到达P的最右字符移出T为止.

: P="aaaba", T="aaabbaaaba", 则匹配过程如下图

 T:     a   a   a   b   b   a   a   a   b  a
 P:     a   a   a   b   a                                                                 

            a   a   a   b   a                 
                                .....
                            a   a   a   b  a            

从上不难分析,最坏的情况是"每次比较都在最后一个字符出现不等,每趟最多比较M,最多比较N-M+1,总的比较次数最多为M*(N-M+1)" ,时间复杂性为0(M*N). P右移一位时,不管上一趟比较的中间结果是什么,因此回溯是不可避免的(: 3aaa 不需要一位一位的移 ) .下面我来介绍无回溯的KMP算法.


3.KMP
算法解决匹配中哪些主要问题
A.
当字符串比较出现不等时,确定下一趟比较前 应该将P右移多少个字符
B. P
右移后,应该从哪个字符开始和T中刚才比较时不等的那个字符继续开始比较.

   
我们通过朴素模式匹配的例子来引出问题. 在第一次比较过程中失败的是P的第4个字符b,这表明P的前4个字符是成功的.模式P的第3个字符b在它的前3个字符(aaa)中并未出现.因此,在下一次比较时候,至少要将P向后移4个字符; 再看P的第一个字符与最后一个字符是相同的因此将P右移4个字符后 再从第一个字符比较 可定也是不等的综上所诉:应该将P右移5个字符 再从P的第0个字符和T的第5个字符开始比较!

KMP
算法核心: KMP算法借助于一个辅助数组next来确定当匹配过程中出现不等时,模式P右移的位置和开始比较的位置.next[i]的取值只与模式P本身的前i+1项有关,而与目标T无关.     匹配过程中遇到Pi不等于Tj,next[i]>=0,则应将P右移i-next[i]位个字符,P中的第next[i]个字符与Tj 进行比较;:next[i]= -1,P中的任何字符都不必再与Tj比较,而应将P右移i+1个字符,P0Tj+1从新开始下一轮比较(可能不太好理解,自己找个例子,对着话一句一句试试看)
 
 
因此只要计算出与模式P相关的next数组,按上面的含义,就可以很容易地给出串的匹配算法.(问题就这样转化了)

 C.next
的计算P = " 01001010100001"为例.

  i   :            0   1   2   3   4   5   6    .....  
  P   :            0   1   0   0   1   0   1    .....

 j(next[i]) :     -1   0   0   1   1   2   3    .....

修正(next[i])  :  -1   0  -1   1   0  -1   3    .....
例子中的j(next[i])为未修正前的next数组(关于修正我会在下次提到).
1:我们要算next[2]的值,有关的为P本身的前2个字符0,1.   在字符串01,寻找出   "左右相同的最大字符串,此字符串所含字符的个数就为next[i]的值"0不等于1,相同字符串不存在,所以next[i] = 0;

2:我们要算next[6]的值,有关的为P本身前6个字符010010  此字符串中010 = 010
左右相同的最大字符串为010,个数为3.所以next[i]=3;

3:我们要算next[5]的值,有关的为P本身前5个字符01001 此字符串中 01=01 左右相同的最大字符串为01,个数为2.所以next[i]=2;


通过上面的例子大家应该有所了解了,有什么问题可以留言给我.

                       

             
             KMP
的算法     VC++6.0

 

Cmystring::GenKMPNext(int *next, CMyString *s)

{ int i=0; j=-1;

   next[0]=-1;

 while(i<s->length)

  {

  while(j>=0&&s->str[i]!=s->str[j])

     j=next[j];

   i++;j++;

   if(s->str[i]==s->str[j])

      next[i]=next[j];
  else  next[i]=j;}

}


///////////////////
串类的find()方法 KMP匹配算法////////////////////////
int CMyString::find(const CMyString *S)
{
    int i , j , *next = new int[s->length];
    GenKMPNext(next, s);
    for(i= 0,j=0;i< s->length&&j<length;)
    {
        if( s->str[i] = =str[j] ) { i++ , j++;}
        else
            if(next[i] >=0)
                 i = next[i];
            else
            { i = 0; j++}
     }
     if(i>= s->length)
       return  j - s->length;
     else
          return -1;
}


                

posted on 2006-10-10 21:58 冬天¤不回来 阅读(11285) 评论(15)  编辑 收藏 引用

FeedBack:
# re: KMP算法初学
2006-10-10 22:03 | 冬天¤不回来
今天真是郁闷,一下课就回来开门造车,写KMP,花了3个小时写了个很好的,结果一发表出去 却变成一堆乱78糟的东西!!可能是因为颜色 下标 大小写等搞混淆了! 然后又花了40分钟,删的删,改的改,最后出来这个让我无语的版本.痛苦ED.
虽然删了些,但精华还在,希望对大家有帮助.  回复  更多评论
  
# re: KMP算法初学
2006-12-29 22:06 | lily1115
没有啊!很有特色!  回复  更多评论
  
# re: KMP算法初学
2007-01-04 20:30 | pengkuny
博主,能不能换个模板?
看着实在难受  回复  更多评论
  
# re: KMP算法初学
2007-04-14 16:03 | hotjuly
@冬天&#164;不回来
今天真是郁闷,一下课就回来开门造车,写KMP,花了3个小时写了个很好的,结果一发表出去 却变成一堆乱78糟的东西!!可能是因为颜色 下标 大小写等搞混淆了! 然后又花了40分钟,删的删,改的改,最后出来这个让我无语的版本.痛苦ED.
====================================================================
诶,这个排版。。。
够郁闷的,精神可嘉。
楼主可以在word中全部搞定,然后转换成html的,然后从html全部复制到blog上,这样排版应该没问题了。比较重要的文章可以转换成pdf,提供下载,可以让读者线下浏览。www.51files.com 不错的
btw:你们一帮人都在搞算法,什么专业的?  回复  更多评论
  
# re: KMP算法初学
2008-10-10 20:23 | yjw
写得太好了   回复  更多评论
  
# re: KMP算法初学
2008-12-05 11:57 | hf
写的确实不错啊!!  回复  更多评论
  
# re: KMP算法初学[未登录]
2009-09-30 08:37 | 123
有错误  回复  更多评论
  
# re: KMP算法初学
2011-09-02 21:51 | ROSALINDA19Wolfe
People deserve good life and <a href="http://bestfinance-blog.com/topics/personal-loans">personal loans</a> or auto loan can make it better. Just because freedom bases on money.   回复  更多评论
  
# re: KMP算法初学
2011-11-03 16:57 | nono
@冬天&#164;不回来
思想还是错了..  回复  更多评论
  
# re: KMP算法初学
2015-09-10 15:15 | taruhan bola;judi bola;agen bola;sbobet;judi onlin
For instance, coffee shops have menus of brown color or shades of the same hue in order to bring the atmosphere of the cafe and set it in the menu. Whereas, a Japanese or Chinese restaurant would make a more colorful menu that uses images that reflect their culture and their food – since their dishes include various colors. This blog will be showing you some of the most amazing menu designs for your use.I seriously appreciate people like you! Take care!!;)!!visit my site and Play  回复  更多评论
  
# re: KMP算法初学
2015-09-10 15:16 | taruhan bola;judi bola;agen bola;sbobet;judi onlin
The you have is very useful. The sites you have referred was good. Thanks for sharing....  回复  更多评论
  
# re: KMP算法初学
2015-09-10 15:17 | taruhan bola;judi bola;agen bola;sbobet;judi onlin
I really appreciate the kind of topics post here. Thanks for sharing us a great information that is actually helpful. Good day! nirmala.cutez@yahoo.com  回复  更多评论
  
# re: KMP算法初学
2015-09-10 15:18 | nagapoker;poker online;game poker:poker indonesia;
This is a very good post. Just wonderful. Truly, I am amazed at what informative things you've told us today  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


QQ:41696402

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(3)

随笔档案

文章档案

Programming

最新随笔

搜索

  •  

积分与排名

  • 积分 - 38473
  • 排名 - 534

最新评论

阅读排行榜

评论排行榜