字符串匹配的KMP算法
##coding: utf-8
##kmp算法是一个快速字符串查找匹配算法
##思路是: 母串指针i,模式串指针j;
##能匹配时,i,j指针都向前走;不匹配时,i指针不动,j指针回溯
## if s==m[j]:
## i+=1
## j+=1
## else:
## j回溯
##j指针回溯,也就是模式串向前滑动,滑动距离要尽可能短,以免错过合适的匹配位置
##(所有的教科书上都说是'尽可能长的距离';
## 但我经过分析后认为,在保证i指针不动的情况下,滑动的距离应该说是尽可能短)
##
##如何决定这一"尽可能短"呢?
##办法是:
##先要求出一个名为next的列表, 在这个列表中记录着对应j不匹配时去处:
##不匹配时, j指针回溯到对应的next[j]处就可以了
## next=get_next(..)
## if s==m[j]:
## i+=1
## j+=1
## else:
## j=next[j]
##
##
## next值只决定于模式串,与母串无关; 要看出这点并不容易.
##
##next[j]=x隐含如下信息:
# m[j]!=s (a)
# m[1..j-1]=s[i-j+1..i-1] (1)
# m[1..x-1]=s[i-x+1..i-1],其中xj (2)
# 且不存在j>y>x, 使得(2)成立,所谓滑行尽可能短的距离(b)
##
## 由(1), 得 s[i-x+1..i-1]=m[j-x+1..j-1] (3)
## 由(2),(3), 得 m[1..x-1]=m[j-x+1..j-1] (c)
##
## 得到的(c)式与母串s无关, 而满足(c)式是j指针能回溯到x的必要条件
##
##
##
## 求next的过程也是个匹配过程,这个匹配也是kmp算法匹配
## 在get_next函数中,母串和模式串都是m, 进行匹配
## i指针指向母串,j指针指向模式串
## 在满足(c)的情况下填写下一个next[],所谓只决定于模式串
## 在不满足时(c)时,充分利用前面得到的next[],进行kmp匹配
##
## (以下讨论中,所有index都按python特点,与上面有差异)
##
## 首先注意, 在get_next函数中,由于模式串和母串是相同的,
## 所以i,j指针的初始值必须错开一位,才有意义
## i,j初始值分别应该是1和0;
## 其次注意, 遇到j等于0，不匹配时，j指针应该不回溯(无处可去)，
## 而应该使i指针加1。这样的话，这里的next[i+1]就被空过不填, 这是不应该的;
## 事实上,这时的next[i+1]应该等于0.
## 然后注意, 因为i初始为1,所以next[0]和next[1]不会被自动填上,只能事先给出
## next[0]是无用的,添了'none'; next[1]等于0.
def get_next(m):
i,j=1,0
next=range(len(m))
next[0]='none'
next[1]=0
while ilen(m)-1:
if m==m[j]:
i+=1
j+=1
next=j
elif j==0:
i+=1
next=0
else:
j=next[j]
return next
##现在来证明get_next函数的可行性:
## len(m)应与len(next)相等,next=range(len(m))保证了next有足够空间
## 而每比较m和m[j]时,得到的是next[i+1],这要求while循环到i=len(m)-1为止,
## 因此ilen(m)-1,保证不会丢落,也不会越界
## 以i为计数器循环, 每次或者i加1,这时填好对应next[i+1];
## 或者i不变,j回溯; i总是比j大, 保证j回溯时, next[j]已填上.
##get_next函数有效性的证明:
## 前面讲述过,在get_next函数中以模式串匹配模式串,保证了条件(c)的成立.
## 在kmpsearch函数中看到,应用next[j]前, 条件(a)和(1)成立, 结合条件(c)
## 推知回溯后条件(2)成立; 这里唯一剩下的是条件(b)
## 条件(b)要求next值尽可能大, 或者说滑行尽可能短
## 我们知道,在get_next函数中匹配时,模式串也是从左往右滑,
## 在一个固定的i点,一旦满足(c),next[i+1]马上被填好,这就保证了滑行尽可能短
####get_next('abaabcac')
## 下面是对应的主kmp程序, 初始时,i,j都是零
## 如果对应相等,往前走;
## 否则,如果j指针是零, j不回溯, i向前,
## 如果j不是零,则j等于next[j]
def kmpsearch(s,m):
i,j=0,0
next=get_next(m)
print 'next: ', next
while ilen(s) and jlen(m):
if s==m[j]:
i+=1
j+=1
elif j==0:
i+=1
else:
j=next[j]
if j>=len(m):
print "Succeed at index ", i-len(m)," !"
else:
print "mode NOT found !"
##所有教科书的代码用了个巧妙的办法:
##当不匹配且j等于零时，j回溯到-1，表示这一特殊的情况;
##要做到这点,并不需要开辟新的if分支,只要拿废置不用的next[0]来保存-1
## next[0]=-1
##j等于零的不匹配被当作普通不匹配,有:
## j=next[j]
##相当于: j=next[0]
##j的值就变成了-1.
##然后，有这种特殊标志的情况与已经匹配的情况同等处理:
## if j==-1 or m=m[j]:
## i+=1
## j+=1
## next=j
##相当于: if j==-1:
## i+=1
## j=0
## next=0
##改进后的get_next如下:
##def get_next(m):
## i,j=1,0
## next=range(len(m))
## next[0]=-1
## next[1]=0
## while ilen(m)-1:
## if j==-1 or m==m[j]:
## i+=1
## j+=1
## next=j
## else:
## j=next[j]
## return next
##事实上,教科书上的代码是: i,j的初始值分别为0,-1
##这样,next[1]的值也会自动填好
##对应的主kmp程序
##def kmpsearch(s,m):
## i,j=0,0
## next=get_next(m)
## while ilen(s) and jlen(m):
## if j==-1 or s==m[j]:
## i+=1
## j+=1
## else:
## j=next[j]
## if j>=len(m):
## print "Succeed at index ", i-len(m)," !"
## else:
## print "mode NOT found !"
kmpsearch('abaabaabcacbb','abaabcac')
## 该算法的特点是: 匹配过程中,i指针不回溯,只有j指针回溯. 这样匹配会更快一些
