勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

KMP 算法笔记

KMP算法是查询子串比较快的一种算法!

我们先看普通的模式匹配算法。。
int Index(String S,String T,int pos)//参考《数据结构》中的程序
{
  i
=pos;j=1;//这里的串的第1个元素下标是1
  while(i<=S.Length && j<=T.Length)
  {
    
if(S[i]==T[j]){++i;++j;}
    
else{i=i-j+2;j=1;}//**************(1)
  }
  
if(j>T.Length) return i-T.Length;//匹配成功
  else return 0;
}
匹配的过程非常清晰,关键是当‘失配’的时候进行回溯!

看下面的例子:

S:aaaaabababcaaa  T:ababc

aaaaabababcaaa
    ababc.(.表示前一个已经失配)
回溯的结果就是
aaaaabababcaaa
     a.(babc)
如果不回溯就是
aaaaabababcaaa
        aba.bc
这样就漏了一个可能匹配成功的情况
aaaaabababcaaa
      ababc



为什么会发生这样的情况?这是由T串本身的性质决定的,是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的,大没有回溯的必要。

改进的地方也就是这里,我们从T串本身出发,事先就找准了T自身前后部分匹配的位置,那就可以改进算法。

如果不用回溯,那T串下一个位置从哪里开始呢?

还是上面那个例子,T为ababc,如果c失配,那就可以往前移到aba最后一个a的位置,像这样:
...ababd...
   ababc
   ->ababc

这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是KMP算法所在。这个当T[j]失配后,j应该往前跳的值就是j的next值,它是由T串本身固有决定的,与S串无关。

《数据结构》上给了next值的定义:
          
0   如果j=1
next[j]
={Max{k|1<k<j且'p1pk-1'='pj-k+1pj-1'
          
1   其它情况

我当初看到这个头就晕了,其实它就是描述的我前面表述的情况,关于next[1]=0是规定的,这样规定可以使程序简单一些,如果非要定为其它的值只要不和后面的值冲突也是可以的;而那个Max是什么意思,举个例子:

T:aaab

...aaaab...
   aaab
  ->aaab
   ->aaab
    ->aaab

像这样的T,前面自身部分匹配的部分不止两个,那应该往前跳到第几个呢?最近的一个,也就是说尽可能的向右滑移最短的长度。

OK,了解到这里,就看清了KMP的大部分内容,然后关键的问题是如何求next值?先不管它,先看如何用它来进行匹配操作,也就是说先假设已经有了next值。

将最前面的程序改写成:

int Index_KMP(String S,String T,int pos)
{
  i
=pos;j=1;//这里的串的第1个元素下标是1
  while(i<=S.Length && j<=T.Length)
  {
    
if(j==0 || S[i]==T[j]){++i;++j;} //注意到这里的j==0,和++j的作用就知道为什么规定next[1]=0的好处了
    else j=next[j];//i不变(不回溯),j跳动
  }
  
if(j>T.Length) return i-T.Length;//匹配成功
  else return 0;
}

OK,是不是非常简单?还有更简单的,求next值,这也是整个算法成功的关键,从next值的定义来求太恐怖了,怎么求?前面说过了,next值 表达的就是T串的自身部分匹配的性质,那么,我只要将T串和T串自身来一次匹配就可以求出来了,这里的匹配过程不是从头一个一个匹配,而是从T[1]和T [2]开始匹配,给出算法如下:

void get_next(String T,int &next[])
{
  i
=1;j=0;next[1]=0;
  
while(i<=T.Length)
  {
    
if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/}
    
else j=next[j];
  }
}
注意到(2)语句逻辑覆盖的时候是T[i]==T[j]以及i前面的、j前面的都匹配的情况下,于是先自增,然后记下来next[i]=j,这样每当i有 自增就会求得一个next[i],而j一定会小于等于i,于是对于已经求出来的next,可以继续求后面的next,而next[1]=0是已知,所以整 个就这样递推的求出来了,方法非常巧妙。

posted on 2008-12-06 10:23 expter 阅读(228) 评论(0)  编辑 收藏 引用 所属分类: 其他学习笔记算法与数据结构


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理