字符串匹配算法

♂樱♀

我们假设要在字符串dest里寻找子串op。OK，展开我们的讨论。

传统的匹配算法是从dest的开头与op进行比较，若匹配就返回true，若不匹配就从dest的下一个字符开始继续匹配。可以想象，若dest的长度是N，op的长度是M，这将是O(M*N)的时间复杂度。确实比较难以接受。于是我考虑了以下算法。

首先仍然是从dest的开头进行匹配，若遇到某个字符不匹配，那么我们就从该字符的下一个字符开始匹配。为什么可以这么做？很好理解。手画一下，假设是从p处开始进行匹配，在q处失配，那么你可以看到，把op在p到q内向右平移，不管怎么移动都是不会匹配的。手画一下就很好理解了。那么基于以上原理，我们可以进行以下算法。可以在O(M+N)的时间复杂度内匹配执行完毕……似乎是这个复杂度～呵呵



StringSubString PROC FAR



获得dest与op的长度

初始化p＝0



While (dest[p]!=’\0’)

Begin

从p开始匹配op

如果在i处（距op头的偏移量）不匹配

Begin

  if(i==0) ++pos
else
  Pos+=i

Else //字符仍然匹配

  如果i已经是op的最后一个字符了 那么显然匹配成功 ，return true

End

End



Return false

StringSubString ENDP



这就是我写出的伪代码……顺便附上可执行的代码。考虑到这种字符串操作、内存操作这类函数非常常用，所以个人觉得有汇编写的必要。看了一下VS.NET 2003生成的汇编代码，在release下打开所有可能优化选项代码还比较满意。其他情况……略…… DDD

本人语文还是比较差滴……所以有什么错误和问题，请让我知道……谢谢



樱，于2005-3-24 清晨8点2夜没睡时
[em17] [em17]

tarkey

：） 你可以去看看KMP算法，在The Art of Computer Programming一书中有介绍，个人记得好象是在第一卷，网上也有很多KMP的介绍。

logos

难道 tarkey 把 The Art of Computer Programming 看完了？ 厉害！比尔老兄说你看完这套书就可以直接找他面试了...

tarkey

呵呵，我要有功力把那套书看完了，也就不会沉迷与项目和各种实现，而是专心做研究去了。

♂樱♀

早晨迷糊中居然把伪代码写错了……已经做了修正……

Panic

在aaaab中
匹配 aaab的子串。

Panic

http://blog.vckbase.com/panic/archive/2005/03/11/3505.html

♂樱♀

ft。
回头重搞！

游戏战士

KMP强

nasi

<string.H>中有专门的函数 strstr() 就是这个功能，似乎是用KMP写的，O(m+n)的效率