KMP(Python)
作者:
YrMrYu
,
2024-03-14 12:45:39
,
所有人可见
,
阅读 17
def KMP(main_str,sub_str,next_locs):
main_len = len(main_str)
sub_len = len(sub_str)
i, j = 0, 0
result = -1
while i < main_len:
if main_str[i] == sub_str[j]:
if j >= sub_len - 1:
result = i - sub_len + 1
break
i += 1
j += 1
elif next_locs[j] == -1:
i += 1
j = 0
else:
j = next_locs[j]
return result
def next_loc(sub_str):
res = []
sub_len = len(sub_str)
for i in range(sub_len):
if i == 0:
# sub_str的第一位字符的next()值为 -1
res.append(-1)
else:
k = res[i-1]
if sub_str[i-1] == sub_str[k]:
res.append(k+1)
else:
# 迭代查找
while 1:
if k == -1:
res.append(0)
break
if sub_str[i-1] == sub_str[res[k]]:
res.append(res[k]+1)
break
k = res[k]
for i in range(sub_len):
# 对next()进行改进
if res[i] != -1 and sub_str[i] == sub_str[res[i]]:
res[i] = res[res[i]]
pass
return res
def getResult():
s = input() # 子串
l = input() #
if set(s) not in set(l):
return -1
next_locs = next_loc(s)
loc = KMP(l,s,next_locs)
print(loc)
print(getResult())