document.write('

对于字符串的匹配，最直接的方法就是逐个比较字符串中的字符，这种方法比较容易实现，但是效

率也比较低下。对于这种字符串匹配的问题，除了最常见的直接比较法外，经典的KMP算法也是不

二选择，它能够显著提高运行效率，下面分别介绍这两种方法。

方法一：直接计算法

假定主串S=“S0

S2…Sm”，模式串P=“P0

P2…Pn”。实现方法为：比较从主串S中以Si

(0≤i＜m)为首的字符串和模式串P，判断P是否为S的前缀，如果是，那么P在S中第一次出现的位置

则为i，否则接着比较从Si+1开始的子串与模式串P，这种方法的时间复杂度为O(m*n)。此外如果i＞

m-n，那么在主串中以Si为首的子串的长度必定小于模式串P的长度，因此，在这种情况下就没有必

要再做比较了。实现代码如下：

"""

方法功能: 判断p是否为s的子串, 如果是, 那么返回p在s中第一次出现的下标, 否则返回-1

输入参数: s和p分别为主串和模式串

"""

def match(s,p):

#检查参数的合理性

if s==None or p==None:

print "参数不合理"

return -1

slen=len(s)

plen=len(p)

#p肯定不是s的子串

if slen＜plen:

return -1

i=0

j=0

while i＜slen and j＜plen:

if list(s)[i]==list(p)[j]:

#如果相同, 那么继续比较后面的字符

i+=1

j+=1

else:

#后退回去重新比较

i=i-j+1

j=0

if(i＞slen-plen):

return -1

if j＞=plen: #匹配成功

return i-plen

return -1

if__name__=="__main__":

s="xyzabcd"

p="abc"

print match(s,p)

程序的运行结果为：

算法性能分析：

这种方法在最差的情况下需要对模式串P遍历m-n次(m，n分别为主串和模式串的长度)，因此，

算法的时间复杂度为O(n(m-n))。

方法二：KMP算法

在方法一中，如果“P0

P2…Pj-1”==“Si-j…Si-1”，那么模式串的前j个字符已经和主串中i-j

到i-1的字符进行了比较，此时如果Pj

!=Si，那么模式串需要回退到0，主串需要回退到i-j+1的位置

重新开始下一次比较。而在KMP算法中，如果Pj

!=Si，那么不需要回退，即i保持不动，j也不用清

零，而是向右滑动模式串，用Pk和Si继续匹配。这种方法的核心就是确定k的大小，显然，k的值越

大越好。

如果Pj

!=Si，可以继续用Pk和Si进行比较，那么必须满足：

(1)“P0

P2…Pk-1”==“Si-k…Si-1”

已经匹配的结果应满足下面的关系：

(2)“Pj-k…Pj-1”==“Si-k…Si-1”

由以上这两个公式可以得出如下结论：

“P0

P2…Pk-1”=“Pj-k…Pj-1”

因此，当模式串满足“P0

P2…Pk-1”==“Pj-k…Pj-1”时，如果主串第i个字符与模式串第j个字

符匹配失败，那么只需要接着比较主串第i个字符与模式串第k个字符。为了在任何字符匹配失败的

时候都能找到对应k的值，这里给出next数组的定义，next[i]=m表示的意思为：“P0P1…Pm1”=“Pi-m…Pi-2Pi-1”。计算方法如下：

(1)next[j]=-1 (当j==0时)

(2)next[j]=max (Max{k|1＜k＜j且“P0…Pk”==“Pj-k-1…Pj-1”)

(3)next[j]=0 (其他情况)

实现代码如下：

"""

方法功能: 求字符串的next数组

输入参数: p为字符串, nexts为p的next数组

"""

def getNext(p,nexts):

i=0

j=-1

nexts[0]=-1

while i＜len(p):

if j==-1 or list(p)[i]==list(p)[j]:

i+=1

j+=1

nexts[i]=j

else:

j=nexts[j]

def match(s,p,nexts):

#检查参数的合理性, s的长度一定不会小于p的长度

if s==None or p==None:

print "参数不合理"

return -1

slen=len(s)

plen=len(p)

#p肯定不是s的子串

if slen＜plen:

return -1

i=0

j=0

while i＜slen and j＜plen:

print "i="+str(i)+","+"j="+str(i)

if j==-1 or list(s)[i]==list(p)[j]:

#如果相同, 那么继续比较后面的字符

i+=1

j+=1

else:

#主串i不需要回溯, 从next数组中找出需要比较的模式串的位置j

j=nexts[j]

if j＞=plen: #匹配成功

return i-plen

return -1

if __name__=="__main__":

s="abababaabcbab"

p="abaabc"

lens=len(p)

nexts=[0]*(lens+1)

getNext(p,nexts)

print "nexts数组为: "+str(nexts[0]),

i=1

while i＜lens-1:

print ","+str(nexts[i]),

i+=1

print \'\\n\'

print "匹配结果为:"+str(match(s,p,nexts))

程序的运行结果为:

next数组为:-1,0,0,1,1

i=0,j=0

i=1,j=1

i=2,j=2

i=3,j=3

i=3,j=1

i=4,j=2

i=5,j=3

i=5,j=1

i=6,j=2

i=7,j=3

i=8,j=4

i=9,j=5

匹配结果为：4

从运行结果可以看出，模式串P="abaabc"的next数组为[-1,0,0,1,1]，next[3]=1，说明

P[0]==P[2]。当i=3，j=3的时候S[i]!=P[j]，此时主串S不需要回溯，跟模式串位置

j=next[j]=next[3]=1的字符继续进行比较。因为此时S[i-1]一定与P[0]相等，所以，就没有必要再

比较了。

算法性能分析：

这种方法在求next数组的时候循环执行的次数为n(n为模式串的长度)，在模式串与主串匹配的过

程中循环执行的次数为m(m为主串的长度)。因此，算法的时间复杂度为O(m+n)。但是由于算法申

请了额外的n个存储空间来存储next数组，因此，算法的空间复杂度为O(n)。

');