字符串查找
2018-03-20 本文已影响4人
只为此心无垠
def strStr(self, source, target):
# write your code here
if source == None or target == None:
return -1
n = len(source)
m = len(target)
if (n == 0 and m == 0) or m == 0:
return 0
if n == 0 or n < m:
return -1
i, j = 0, 0
while i < n - m + 1:
while j < m:
if source[i+j] == target[j]:
if j == m-1:
return i
else:
j += 1
else:
i = i+1 #i只能一步步向后移动
j = 0
break
return -1
KMP其实只改进了i的移动速度，不是一步步向后，可能是多步
#生成next表
def partial_table(self, p):
prefix = set() #前缀
postfix = set() #后缀
ret = [0]
for i in range(1,len(p)):
prefix.add(p[:i])
postfix = {p[j:i+1] for j in range(1,i+1)}
# 前缀后缀最长公共元素长度
ret.append(len((prefix&postfix or {''}).pop()))
return ret
def strStr(self, source, target):
# 边界条件判断
if source == None or target == None:
return -1
n = len(source)
m = len(target)
if (n == 0 and m == 0) or m == 0:
return 0
if n == 0 or n < m:
return -1
#初始化next表
nextList = self.partial_table(target)
i, j = 0, 0
#开始循环
while i < n - m + 1:
while j < m:
if source[i+j] == target[j]:
if j == m-1:
return i
else:
j += 1
else:
if (j - nextList[j - 1]) + i > n - m:
break
#核心差距在这里，其他代码一致
i = max((j - nextList[j - 1]), 1) + i #i多步向后移动，唯一和第一个程序不一样的地方
j = 0
break
return -1
