KMP & BM

##KMP & BM ###小问题字符串abcabd
a的后缀[a, ab, abc, abca, abcab, abcabd] b的前缀[b,ab]
求各个字符的前缀与第一个字符a的后缀完全相同的最大长度，例如第二个b的前缀ab与a的后缀ab相同

t[] = abcabd
p[] = [-1, -1, -1, 0, 1, -1]表示t[i]字符与a的后缀匹配下标

####递推公式
如果t[p[i-1] + 1] == p[i]则p[i] = p[i-1] + 1
如果t[p[i-1] + 1] != p[i]则比较t[p[p[i-1]] + 1] 和 p[i]，不断嵌套直到两者相等，因为p[i-1]能保证得到t[i-1]最长后缀

###正题字符串s:abcabcabd
匹配串t:abcabd
当t[5]‘d’匹配到s[5]‘c’，匹配失败，
效率低的方法：
t向右移一位，然后重新从a开始和s匹配，s,t的下标从0开始
KMP:
可以略过t[5-1]的前缀和t[0]后缀相同部分ab，让t向右移动两位,且从c开始匹配，而s的小标也无需改变继续匹配

##BM Boyer-Moore算法效率比KMP高,各种文本编辑器的查找功能都是采用该算法.
###匹配策略
####坏字符规则

模式串与被匹配串具有相同后缀,把该后缀称为好后缀

若模式串中有好后缀的相同子串,移动pattern对齐该好后缀

模式串的最长前缀等于好后缀,移动pattern对齐该好后缀

不满足以上条件则移动整个模式串长度距离

(还有一种情况:找好后缀的后缀在模式串中的子串,该情况没有意义,因为如果该子串不是被匹配串的前缀,移动模式匹配串到对齐位置一定是不合理的.而如果该子串是被匹配的前缀,移动即合理,符合情况三)

#coding: utf-8
p = [-1]
def ini(pattern):
	for i in range(1, len(pattern)):
		if pattern[i] == pattern[0]:
			p.append(0)
		else:
			p.append(-1)

		j = i - 1
		while(j != -1):
			if pattern[p[j] + 1] == pattern[i]:
				p[i] = p[j] + 1
				break
			else:
				j = p[j]
	#print p

def kmp(s, t):
	ini(t)
	j = 0
	i = 0
	while(i != len(s)):
		while(j != len(t)):
			if t[j] == s[i]:
				j = j + 1
				i = i + 1 
			else:
				if j == 0:
					i = i + 1
					break
				j = p[j - 1] + 1 
		if j == len(t):
			return 1
	return 0

preGS = []
GS = []
BC = {}
#O(n^2/2)
def pre_build(pattern):
	#以i为右边界与后缀相同的字符个数
	for i in range(len(pattern)):
		GS.append(-1)
		t = i
		j = len(pattern) - 1
		while(j >= 0 and t >= 0 and t != j):
			if pattern[t] == pattern[j]:
				t = t - 1
				j = j - 1
			else:
				break
		preGS.append(i - t)
	#print 'preGS', preGS

def build_good_shuffix(pattern):
	pre_build(pattern)

	#情况三,模式串的前缀=后缀
	for i in range(len(pattern)):  

##		if preGS[i] == i + 1:
			#最左的后缀字符下标
##			GS[len(pattern) - preGS[i]] = len(pattern) - preGS[i]
	#情况二,模式串的子串=后缀
##	for i in range(len(pattern)):
    #情况二和三,同下代码
    #等式右边表示模式串移动多少距离
	    if preGS[i] != 0:
			GS[len(pattern) - preGS[i]] = len(pattern) - preGS[i]
	#print 'GS' ,GS


def build_bad_char(pattern):
	for i in range(len(pattern)):
			BC[pattern[i]] = i
	#print 'BC', BC

def bm(s, t):
	build_good_shuffix(t)
	build_bad_char(t)
	if len(s) < len(t):
		return False
	i = len(t) - 1
	j = len(t) - 1
	while(i < len(s)):
		while(j >= 0):
			if s[i] == t[j]:
				i = i - 1
				j = j - 1
			else:
				break
		if j == -1:
			return True
		else:
			skip = GS[j]
			if(BC.has_key(s[i])):
				if BC[s[i]] < j:
					skip = max(skip, j - BC[s[i]])
			if skip <= 0:
				skip = len(t)
		#print 'skip', skip

		i = i + skip
		j = len(t) - 1	
		#print 'i', i
		#print 'j', j
	return False
		

if __name__ == '__main__':
	print kmp('faeadsfasdfcasdfasdfasdfabcxsdfsadfadfxdesadffeabcxxxabcdwawasdfsdfsaasdf', 'abcxxxabc')
	print bm('faeadsfasdfasaewcaasdfasdfdbcxsdfsadfadfxdesadffeabcxxxabcdwawasdfsdfsaasdf', 'abcxxxabc')