2024.6.14刷题记录-KMP记录

本文主要是介绍2024.6.14刷题记录-KMP记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、831. KMP字符串 - AcWing题库

1.普通版KMP

2.代码简洁版KMP

---

一、831. KMP字符串 - AcWing题库

1.普通版KMP

学习记录（http://t.csdnimg.cn/JxPv5）。解题代码如下：

# KMP算法
# 创建next数组
def build_next(patt):i = 1n = len(patt)prefix_len = 0next = [0] * nwhile i < n:if patt[prefix_len] == patt[i]:# 匹配成功，继续匹配后面的prefix_len += 1next[i] = prefix_leni += 1else:# 匹配失败if prefix_len == 0:# 匹配下一个# next.append(0)i += 1else:# 跳转prefix_len = next[prefix_len - 1]return nextpatt_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 += 1j += 1elif j > 0:# 跳转j = next[j - 1]else:# 一点不匹配i += 1if 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 += 1next[i] = j# 字符串匹配j = 0for 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 += 1if j == patt_len:print(i - j, end = ' ') # i+1-j-1 = i-jj = next[j]

完

感谢你看到这里！一起加油吧！

这篇关于2024.6.14刷题记录-KMP记录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---