题意：给出两个字符串s和t，求t在s中出现的个数
思路：用kmp算法，在第一次匹配(t,s)后，如果t的前缀和后缀一样，就可以直接将s移动到与后缀匹配的位置，不必只一位一位的移
代码如下：
def fail(sub_string):
ans = [0] * (len(sub_string) + 1)
for i in range(1, len(sub_string)):
j = ans[i]
while j > 0 and sub_string[i] != sub_string[j]:
j = ans[j]
if sub_string[i] == sub_string[j]:
ans[i + 1] = j + 1
else:
ans[i + 1] = 0
return ans
def count_substring(string, sub_string):
next = fail(sub_string)
cnt = 0
start = 0
length = len(string) - len(sub_string)
i = 0
while i <= length:
while start < len(sub_string) and string[i + start] == sub_string[start]:
start = start + 1
if start == len(sub_string):
cnt = cnt + 1
i = i + start - next[start]
if next[start] == 0:
i = i + 1
start = next[start]
return cnt
if __name__ == "__main__":
string = input().strip()
sub_string = input().strip()
count = count_substring(string, sub_string)
print(count)
版权声明：本文为wuli2496原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。