BF算法和KMP算法 python实现
BF算法
def Index(s1,s2,pos = 0):
""" BF算法 """
i = pos
j = 0
while(i < len(s1) and j < len(s2)):
if(s1[i] == s2[j]):
i += 1
j += 1
else:
i = i - j + 1
j = 0
if(j >= len(s2)):
return i - len(s2)
else:
return 0
if __name__ == "__main__":
s1 = "ababcabcacbab"
s2 = "abcac"
print(Index(s1,s2))
KMP算法
# KMP算法
def Index_KMP(s1,s2,pos=0):
next = get_next(s2)
i = pos
j = 0
while(i < len(s1) and j < len(s2)):
if(j == -1 or s1[i] == s2[j]):
i += 1
j += 1
else:
j = next[j]
if(j >= len(s2)):
return i - len(s2)
else:
return 0
def get_next(s2):
i = 0
next = [-1]
j = -1
while(i <len(s2)-1):
if(j == -1 or s2[i] == s2[j]):
i += 1
j += 1
next.append(j)
else:
j = next[j]
return next
if __name__ == "__main__":
s1 = "acabaabaabcacaabc"
s2 = "abaabcac"
print(Index_KMP(s1,s2))
版权声明：本文为zrdm原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。