将两个串 A 和串 B，依次循环实现两个串的模式匹配过程
def BF(s,p):
# 判断串p在不在串s中
n1 = len(s)
n2 = len(p)
i,j = 0,0
while i < n1 and j < n2:
if s[i] == p[j]:
i += 1
j += 1
else:
i = i - j + 1
j = 0
if j == n2:
return i - j
else:
return -1
if __name__ == "__main__":
result = BF("abcab","cab")
print(result)
""" results: 2 """KMP算法
KMP算法原理讲解
大家可以看上面链接的视频，来了解KMP算法的原理，下面是代码
def get_next(p):
next = [0]
now = 0
x = 1
while x < len(p):
if p[now] == p[x]:
now += 1
x += 1
next.append(now)
elif p[now] != p[x] and now != 0:
now = next[now-1]
elif p[now] != p[x] and now == 0:
next.append(0)
x += 1
return next
def KMP(s,p):
i,j = 0,0
next = get_next(p)
while i < len(s) and j < len(p):
if s[i] == p[j]:
i += 1
j += 1
elif s[i] != p[j] and j != 0:
j = next[j-1]
elif s[i] != p[j] and j == 0:
i += 1
if j == len(p):
return i-j
else:
return -1
if __name__ == "__main__":
result = KMP("abcab","cab")
print(result)
