KMP字符串 Python3
介绍kmp算法的帖子太多了,这里只记录一下python实现的kmp算法
整体思路与各帖子类似
from sys import stdin
def get_next(pat):
next = [0]
j = 0
for i in range(1, len(pat)):
while j > 0 and pat[j] != pat[i]: j = next[j - 1]
if pat[j] == pat[i]: j += 1
next.append(j)
return next
def find_kmp(s, pat):
next = get_next(pat)
res = []
j = 0
for i in range(len(s)):
while j > 0 and pat[j] != s[i]: j = next[j - 1]
if pat[j] == s[i]: j += 1
if j == len(pat):
res.append(i - j + 1)
j = next[j - 1]
return res
def main():
n = int(stdin.readline())
pat = stdin.readline().rstrip()
m = int(stdin.readline())
s = stdin.readline().rstrip()
print(' '.join(map(str, find_kmp(s, pat))))
main()