oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

KMP算法浅析

Posted on 2006-10-10 21:29 oyjpart 阅读(7435) 评论(3)  编辑 收藏 引用
KMP算法是由Knuth, Morris, Pratt三位牛人提出的快速匹配算法 得到了非常的广泛的应用
鉴于最近教材正在学KMP算法 我在此对次算法进行一下简略分析 不清楚的同学可以参考一下
//By Optimistic

说明:字符串查找中,被查找的叫做目标串,查找的叫模式串。如:
            目标串:T[] = 01001010100001 模式串 P[] = 1010
算法来源: 朴素的匹配效率太低。考虑改进:1.当模式串与目标串在i位置比较不同时,下一个应该从目标串的哪里开始比较?2。下一个应该从模式串的哪个开始比较?

于是经过一些简单的逻辑推理 我们得到了KMP算法的思想 让目标串没有回溯 并且模式串尽可能向后滑动

我们用next[i]这个数组来存储当模式串的第i位比较出现不匹配时 模式串的从哪里开始比较
比如next[i] = 2 相当于从从P[2]开始比较 如果next[i] = -1 代表模式串的第一个与目标串的下一个比较

KMP的算法的精华就在于对next[i]的求取,采用next[i-1]=>next[i]的方法求得next[i]的值
下面我们来看看next[i]的求取

string str;
cin >> str;
int * next = new int[str.length()+1];
 int i = 0, j = -1;
 next[0] = -1;
 while(i < str.length())
 {
  while(j>=0 && str[i]!=str[j])
   j = next[j];
  i++;
  j++;
  if(str[i] == str[j]) //修正
   next[i] = next[j];
  else next[i] = j;
}

其中具体的细节其参考 我同寝室同学写的KMP算法详解:
http://www.cppblog.com/warrior0032/archive/2006/10/10/13543.html

其中解释了算法的基本思想和实现过程

我对此算法作几个分析:
1。为什么要修正next[i]值?为什么只要修正一次?
当我们分析到模式串中的第i位于目标串不同时 求得应该从K位开始比较 但是如果第K位于第I位相同的时候 第K位一定与目标串也不同因此应该再次改成当K位比较不同时的NEXT值 即 NEXT[K]
由于NEXT是由左向右推出来的 所以只需修正一次 (数学归纳法?呵呵。。。)

2。程序没有使用一个数组来保存未修正时的NEXT值 而直接用J来充当这个功能 但是J是由NEXT(已修正)得来的 那么有没有可能J得不到正确的值?
这个问题最先是我自己想的 后来验证了一下 J一定能够得到正确的值
下面我们来分析一下
下标                         0  1  2  3  4  5  6  7  8  9 10 11 1213
目标串                     0  1  0  0  1  0  1  0  1  0  0   0   0  1
j(未修正的next)       -1 0  0  1  1  2  3  2  3  2  3   4   1  1
修正了的next          -1 0 -1  1  0 -1  3 -1 3 -1  0  4   1   0

让我们看看但模式串比较到了12位的时候(下标为11)
next[11] = 4; next[4] = 0; j|4 = 1...
这时候next[4]拿到的并不是正确的J值!!!
这会导致什么?会导致略过一个比较 即p[11]与p[1]的比较被略过!直接比较了p[11]与p[0]!
是否可以略过这个比较?!
答案是肯定的.
根据逻辑推理 如果p[11]与p[4]不等 而p[4] = p[1]那么p[11]与p[1]一定不等 所以可以略过
这样说似乎很牵强 我们再回想一下NEXT数组的意义 即当我们比较到i位时不等 应该由哪一位重新开始比较 而实际上 这个过程相当于在 7-11的这个串中查找0-3!所以根据NEXT数组的意义 我们也可以知道 这里并不会导致错误 由于被略去的比较一定不需比较 因此 J始终可以得到正确的未修正的NEXT值!

 3。KMP算法的局限性 由于KMP算法完全由模式串来考虑滑动 可能忽略一些很好的滑动机会
如当目标串某位不同于模式串时 若此目标串中的字符从未在模式串中出现 那么就可以直接滑过去所有的 这时候 目标串也起了   确定滑动距离 的作用.这其实就是BM算法.有兴趣的同学可以参考下列连接
http://www.cnpaf.net/Forum/htm_data/5/0507/1832.html
1977年,Robert Boyer和L.Moore发表了一种新的精确字符串匹配算法,这种算法在逻辑上相对于现有的算法有了很大的超越.它对要搜索的字符串实施逆序字符比较,而且有一种找到了不匹配就不需要对整个字符串进行搜索的方法.这种算法还有最初在PDP-10汇编器上实现的奇迹.

好了 到这里了吧 呵呵 我休息下 最近晕糊涂了

Feedback

# re: KMP算法浅析  回复  更多评论   

2006-10-10 22:05 by 冬天¤不回来
http://www.cppblog.com/warrior0032/archive/2006/10/10/13543.html
这个连接,上面的连接错了!!

# re: KMP算法浅析  回复  更多评论   

2006-10-10 23:01 by Optimistic
o 改过来了

# re: KMP算法浅析  回复  更多评论   

2006-10-11 01:26 by
怎么都搞kmp去了..-_-我们要下学期才能学啊......

不过我看过一篇ioi论文, 好象有比kmp更简洁的匹配, 2003年周源的, 最小数表示法, 同样是o(n)的线性时间:)

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