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))