题解 | #String Matching#
String Matching
https://www.nowcoder.com/practice/00438b0bc9384ceeb65613346b42e88a
def getNext(t):
next = [0] * (len(t)+1)
t = list(t)
i, k = 0, -1
next[0] = -1
while i < len(t):
if k == -1 or t[i] == t[k]:
k+=1
i+=1
next[i] = k
else:
k = next[k]
return next
def kmp(s, t):
i, j = 0, 0
res =0
next = getNext(t)
s = list(s)
t = list(t)
while i < len(s) and j < int(len(t)):
if(j == -1 or s[i] == t[j]):
i+=1
j+=1
else:
j = next[j]
if j == len(t):
res+=1
j = next[j]
#return i - j
return res
# while True:
# try:
s, t = input().split()
res = kmp(s, t)
print(res)
# except:
# break
