手机透明桌面软件:KMP算法真的很简单1

来源:百度文库 编辑:偶看新闻 时间:2024/03/29 21:59:13

KMP算法真的很简单1

分类: C/C++语言 算法艺术 2010-02-03 12:49 1603人阅读 评论(5) 收藏 举报

KMP 算法真的很简单

KMP 是字符串匹配的经典算法,曾经一度对其敬而远之,感觉很难写出来正确的 KMP 算法,这都是拜那些“教科书”所赐,在它们的教授下,不禁感觉 KMP 很难!

其实理解 KMP 算法很简单,今天就来看个究竟,我的目标就是从几个简单的数学等式推导出 KMP 算法,简单但严谨。

串匹配

先来回忆一下串匹配场景,不外乎是给定两个字符串 S 和 T ,然后在 S 串中查找 T 串,如果查找成功就是匹配,否则就是不匹配。比如:

S = “avantar-titanic”; T = “avantar”; C = “tistan” ;那么结果就是 T 匹配 S ,而 C 不能匹配 S 。

朴素的串匹配算法

再来回顾一下朴素的匹配思想,从 S[i] 开始,逐个检查 S[i+pos] 是否与 T[pos] 相等,如果 S[i+pos] = T[pos] ,那么 pos++ ;如果 S[i+pos] != T[pos] ,那么 T 就要回退到 T[0] ,然后再从 S[i+1] 开始尝试匹配 T ,这就是下面的伪代码。

 

view plain

  1. for(int i = 0; i < Len[S]; i++)  
  2. {  
  3.     int j;  
  4.     for(j = 0; j < Len[T]); j++)  
  5.     {  
  6.         if(S[i+j] != T[j]) break;  
  7.     }  
  8.     if(j == Len[T])  
  9.         find T in S  
  10. }  

 

上面算法的问题就在于,如果出现了不匹配的情况, T 就要回退到 T[0] ,算法复杂度为 O(len[S]*len[T]) 。

需要从头再来吗?

让我们来重新审视上面的问题,在 S 串中查找 T 串,我们使用表示法 C [i, j] 表示 C 的字串 S i S i+1 …S j 。 假设当前时刻 S 从位置 i 开始,已经匹配了 pos 个长度,也就是 S[i, i+pos-1] = T[0, pos-1] ,继续向下进行比较;

如果 S[i+pos] = T[pos] ,那么依然有 S[i, i+pos] = T[0, pos] ;

如果 S[i+pos] != T[pos] ,那么将有 S[i, i+pos] != T[0, pos] ;

这时候 朴素的串匹配思想就是回退 T 到 T[0] , 从 S[i+1] 和 T[0] 开始再次逐 字符的比较。然而仔细观察这个时刻,假设我们不让 T 回退到 T[0] ,而是回退到 T[j] 的位置,并让 S 停留在 S[i+pos-1] 的位置,并且满足

S[i+pos-j-1, i+pos-1] = T[0, j] -------------------------(1)

那么必然 j

采用假设法,假设 j 已经找到了,那么等式 (1) 成立。

当匹配进行到 S[i+pos] != T[pos] 时,我们已经有 S[i, i+pos-1] = T[0, pos-1] ,取后面的 j 个字符串就有:

S[i+pos-j, i+pos-1] = T[pos-j, pos-1] ------------------(2)

根据等式 (1) 和等式 (2) ,我们便可得到

T[pos-j, pos-1] = T[0, j] ----------------------------------(3)

也就是说,如果找到了这样的 j ,那么必然满足等式 (3) 。于是我们可以采用一个数组 P ,记住每个 pos 对应的 j ;也就是 P[pos] = j ,当 T[pos] 不能匹配时,就让 T 回退到 j ,继续和 S[i+pos] 匹配; pos 的范围是 0~len[T] 。

如果 j = 0 ,意味着 S[i+pos-1] = T[0] = T[pos-1] ;

如果这个 j 不存在呢,这是很可能发生的,世界不是总是这么美好的嘛,这个时候意味着 S[i+pos-1] != T[0] ,那么我们只能从 S[i+pos] 和 T[0] 开始匹配了。

如果对应于每个 pos 我们都找到对应的 j ,那么不就可以改进上面朴素的匹配算法了吗?姑且把这个结果存储在数组 next 中,于是 next 的定义就是:

next[pos] 表明如果在 pos 处 T[pos] 和 S[m] 不能匹配,但是 T[0, next[pos]] = S[m-next[pos]-1, m-1] 成立,于是应该回退到 T[next[pos]+1] 处和 S[m] 进行匹配。

这时候匹配算法的逻辑就像下面那样:

If S[i] = T[j] then // 如果匹配就继续向后

       i++

       j++

       if j = Len[T] then

              find a match position

       endif

else

       loop // 找到使 S[i] = T[j’] j’

              j = next[j]

until S[i] = T[j] or j < 0

if j < 0 then // j < 0 表明 S[i] != T[0] ,从 i+1 位置匹配 T[0]

       j = -1

endif

i++

       endif

改进后的匹配算法

根据上面的思想,那么我们可以很容易的写出匹配算法的代码。

 

view plain
  1. // search T in S  
  2. int tlen = strlen(T);  
  3. int slen = strlen(S);  
  4. for(int i = 0, j = 0; i < slen;)  
  5. {  
  6.     if(S[i] == T[j]) // 如果S[i]和S[j]匹配,则继续比较S[i+1],T[j+1]  
  7.     {  
  8.         i++;  
  9.         j++;  
  10.         if(j == tlen) // 找到了一个匹配  
  11.         {  
  12.             printf("find [%s] in [%s] at pos %d./n", T, S, i-tlen);  
  13.             j = 0; // 寻找下一个匹配  
  14.         }  
  15.     }  
  16.     else // 如果不匹配,则根据P数组寻找j'  
  17.     {  
  18.          // 直到找到一个j'使得S[i] = T[j'],或者j'=-1  
  19.         while((j >= 0) && (S[i] != T[j]))  
  20.         {  
  21.             j = next[j];  
  22.         }  
  23.         if(j == -1) // j'=-1,表明S[i] != T[0],只能尝试从S[i+1]开始匹配T  
  24.         {  
  25.             j = 0;  
  26.         }  
  27.         i++;  
  28.     }  
  29. }   

 

 

计算next数组

现在另外一个问题出现了,如何求next数组呢?根据前面的分析可以知道next数组只和T串有关,再说一下next的定义:

next[pos]表明如果在pos处T[pos]和S[m]不能匹配,但是T[0, next[pos]] = S[m-next[pos]-1, m-1]成立,于是应该回退到T[next[pos]+1]处和S[m]进行匹配。

最简单的情况开始,next[0]=-1,因为如果T[0] != S[m]那么只能尝试T[0] ? S[m+1];

不难理解,如果T[0] = T[1],那么next[1] = 0,否则next[1] = -1;

对于next[pos] = j 满足T[pos-j, pos-1] = T[0, j],因此可以通过蛮力方法找到这个next数组,只是效率太低,还有更好的方法吗?

如果当前已知next[0],...,next[pos-1],能否通过它们的值来计算next[pos]呢,假设next[pos-1] = j;

1 如果T[j+1] = T[pos],那么结合T[pos-j-1, pos-1] = T[0, j]可知

T[pos-j-1, pos] = T[0, j+1]

于是next[pos] = j+1;

2 如果T[j+1] != T[pos],那么T[pos-j-1, pos] != T[0, j+1],这时候如何求next[pos]呢?假设next[pos] = j’,如果j’ > -1,那么有T[pos-j’, pos] = T[0, j’]。

再考虑对于任意i < pos-1, next[i] = p’, T[i-p’, i] = T[0, p’],那么p’肯定

现在已经有T[pos-j-1, pos-1] = T[0, j],于是T[pos-p’-1, pos-1] = T[0, p’];

如果T[pos] = T[p’+1]的话,就意味着T[pos-p’-1, pos] = T[0,p’+1]

于是next[pos] = next[i] +1;

看来我们找到了求next数组的方法,看看是不是和匹配算法很相似呢,伪代码如下所示:

next[0] = -1

i = 1

j = -1 // j next[0]开始

// 循环直到i=Len[T]

If T[i] = T[j+1] then // 如果匹配就继续向后

       next[i] = j+1 // 计算next[i]

       i++

       j++

else

       loop // 找到使T[i] = T[j’+1]j’

              j = next[j]

until T[i] = T[j] or j < 0

if j < 0 then // j < 0表明T[i] = -1

       next[i] = j = -1

endif

i++

       endif

c++代码如下:

view plain
  1. // 把寻找next数组的过程,看做是T和自身匹配的过程  
  2. void _Next(const char *T, int *next, int tlen)  
  3. {  
  4.     const char *S = T;  
  5.     next[0] = -1;  
  6.     for(int i = 1, j = -1; i < tlen;)  
  7.     {  
  8.         if(S[i] == T[j+1])  
  9.         {  
  10.             next[i] = j+1; // 匹配成功则更新next[i]  
  11.             i++;  
  12.             j++;  
  13.         }  
  14.         else  
  15.         {  
  16.             while((j >= 0) && (S[i] != T[j+1]))  
  17.             {  
  18.                 j = next[j];  
  19.             }  
  20.             if(j == -1)  
  21.             {  
  22.                 next[i] = -1;  
  23.             }  
  24.             i++;  
  25.         }  
  26.     }  
  27. }  

KMP匹配算法

KMP相对于朴素的匹配思想就是当不匹配时,T不必回退到T[0],从而提高了匹配效率。

上面的代码似曾相似啊,其实它就是KMP匹配算法,简单调整一下代码逻辑就和常见的KMP算法相似了。

KMP算法其实不难,几个简单的数学等式就能推出来了嘛,其余的复杂性证明就略过了。