计算字符串t在字符串s中出现的次数(KMP)

  • Post author:
  • Post category:其他


题意:给出两个字符串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 版权协议,转载请附上原文出处链接和本声明。