最近在學(xué)習(xí)子串排序算法枉侧，在此記錄下實(shí)現(xiàn)方式
def bf(string1, string2):
"""
bf
:param string1:
:param string2:
:return:
"""
x, y = 0, 0
while x < len(string1) and y < len(string2):
if string1[x] == string2[y]:
x += 1
y += 1
continue
x = x - y + 1
y = 0
if y >= len(string2):
return x - len(string2)
return 0
def get_next_list(substring):
"""
獲取next列表
:param substring:
:return:
"""
next_list = [0] * len(substring)
x, y = 0, 1
while y < len(substring):
if substring[x] == substring[y]:
x += 1
next_list[y] = x
y += 1
else:
if x == 0:
next_list[y] = 0
y += 1
continue
x = next_list[x - 1]
return next_list
def kmp(string1, string2):
"""
kmp
:param string1:
:param string2:
:return:
"""
x, y = 0, 0
next_list = get_next_list(string2)
while x < len(string1) and y < len(string2):
if string1[x] == string2[y]:
x += 1
y += 1
else:
if y == 0:
x += 1
continue
y = next_list[y]
if y >= len(string2):
return x - len(string2)
return 0
if __name__ == '__main__':
res_kmp = kmp("sdadddababab", "dabab")
print(res_kmp)
