2023年7月20日发(作者：)

计算字符串t在字符串s中出现的次数（KMP）题意：给出两个字符串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 ansdef 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 cntif __name__ == "__main__": string = input().strip() sub_string = input().strip() count = count_substring(string, sub_string) print(count)