首页 > 试题广场 >

kmp算法

[编程题]kmp算法
  • 热度指数：31116 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次

数据范围：
要求：空间复杂度 ，时间复杂度
示例1

输入

"ababab","abababab"

输出

2
示例2

输入

"abab","abacabab"

输出

1
算法知识视频讲解
添加回答
Python3
游客留步牛头像 游客留步牛
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        def pre_process(S):
            '''
            输出前缀表
            '''
            next_string = [0]*len(S)
            j = 0
            for  i in range(1,len(S)):
                while j >0 and S[j] != S[i]:
                    j = next_string[j-1]
                if S[i] == S[j]:
                    j+=1
                next_string[i] = j
            return next_string

        next_string = pre_process(S)
        j = 0  #指向S的当前字符
        count = 0 #记录S在T中出现的次数
        for i  in range(len(T)):
            while j >0 and T[i] !=S[j]:
                j = next_string[j-1]
            if T[i] == S[j]:
                j+=1
            if j == len(S):  #如果把S遍历完全，则视为出现一次
                count +=1
                j = next_string[j-1]
        return count
编辑于 2023-12-21 00:21:56 回复(0)
Python3
牛客832605738号头像 牛客832605738号
#超长字符串超时
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        while True:
            try:
                m=len(S)
                a=0
                for i in range(len(S)+1):     
                    if T[i:i+m]==S:
                        a+=1  
                return a
            except:
                break
发表于 2022-10-20 15:32:00 回复(0)
提交观点

问题信息

字符串
难度：
2条回答 7655浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号