题目描述
blablabla
样例
blablabla
算法1
KMP
主要是next数组的生成,当j = ne[j-1]时,下一个字符还是不相等
那么此时由于j是当前模式串子串的前后缀,则此时想要找更小的前后缀
等同于在该长度的前缀里找最大前后缀,因为后缀的后缀=前缀的前缀=前缀的后缀
时间复杂度
参考文献
Python 代码
n = int(input())
p = input()
m = int(input())
s = input()
ne = [0]*(n+1)
def patern(pa):
j = 0
i = 1
while i<n:
if pa[i]==pa[j]:
ne[i] = j+1
i+=1
j+=1
else:
if j == 0:
i+=1
else:
j = ne[j-1]
j = 0
i = 0
patern(p)
while i<m:
if s[i]==p[j]:
i+=1
j+=1
else:
if j==0:
i+=1
else:
j = ne[j-1]
if j==n:
j=ne[j-1]
print(i-n,end=' ')
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla