目录
一、831. KMP字符串 - AcWing题库
1.普通版KMP
学习记录(http://t.csdnimg.cn/JxPv5)。解题代码如下:
# KMP算法
# 创建next数组
def build_next(patt):
i = 1
n = len(patt)
prefix_len = 0
next = [0] * n
while i < n:
if patt[prefix_len] == patt[i]:
# 匹配成功,继续匹配后面的
prefix_len += 1
next[i] = prefix_len
i += 1
else:
# 匹配失败
if prefix_len == 0:
# 匹配下一个
# next.append(0)
i += 1
else:
# 跳转
prefix_len = next[prefix_len - 1]
return next
patt_len = int(input())
patt = input()
string_len = int(input())
string = input()
next = build_next(patt)
# kmp搜索
i = 0
j = 0
ans = []
while i < string_len:
if string[i] == patt[j]:
i += 1
j += 1
elif j > 0:
# 跳转
j = next[j - 1]
else:
# 一点不匹配
i += 1
if j == patt_len:
# 找到子串
ans.append(i - j)
j = next[j - 1] # 注意这里是跳转
for x in ans:
print(x, end = ' ')
2.代码简洁版KMP
来自题解(AcWing 831. KMP字符串 - AcWing)。通过在字符串前面加一空格,减少j==0这一判断条件。
# 代码更简洁版KMP
if __name__ == '__main__':
patt_len = int(input())
patt = ' ' + input() # 使下标从1开始
string_len = int(input())
string = ' ' + input()
next = [0] * (patt_len + 1)
# next数组
j = 0 # 匹配下标
for i in range(2, patt_len + 1): # 类似主串下标
while j and patt[i] != patt[j + 1]:
# 跳转
j = next[j]
if patt[i] == patt[j + 1]:
# 匹配成功,匹配下标加一
j += 1
next[i] = j
# 字符串匹配
j = 0
for i in range(1, string_len + 1):
while j and string[i] != patt[j + 1]:
j = next[j]
if string[i] == patt[j + 1]:
j += 1
if j == patt_len:
print(i - j, end = ' ') # i+1-j-1 = i-j
j = next[j]
完
感谢你看到这里!一起加油吧!