题目描述
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N,表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M,表示字符串S的长度。
第四行输入字符串M。
输出格式
共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。
数据范围
$1\le N\le10^4$
$1\le M\le 10^5$
代码参考
from array import array
from sys import stdin
def get_dfa(word):
n = len(word)
dfa = array('i', [-1]) * n
i = 0
j = -1
while i < n - 1:
if j == -1 or word[i] == word[j]:
i += 1
j += 1
dfa[i] = j
else:
j = dfa[j]
return dfa
def kmp(pattern, text, n, m):
dfa = get_dfa(pattern)
i = j = 0
while i < m:
if j == -1 or pattern[j] == text[i]:
i += 1
j += 1
else:
j = dfa[j]
if j == n:
print(i-n, end=' ')
j = dfa[j-1] + 1
def main():
n = int(stdin.readline())
pattern = stdin.readline().rstrip()
m = int(stdin.readline())
text = stdin.readline().rstrip()
kmp(pattern, text, n, m)
print()
if __name__ == "__main__":
main()
借楼贴一个正确的KMP python代码:
这个程序好像有BUG:
输入为
程序输出
0 2 6
,但是实际上答案为0 6