江苏龙网

  1. 首页 > 人文 > >

CSDN开玩笑呢？学习KMP算法能改变自我认知？ | 原力计划( 二 )


CSDN开玩笑呢？学习KMP算法能改变自我认知？ | 原力计划
本文插图
已知蓝色区域相等且长度都为len ， 那么很明显 ， next[i] == len ， 若此时模式串pattern[i] != pattern[j]（两个灰色区域不相等） 。 那么看下图：
CSDN开玩笑呢？学习KMP算法能改变自我认知？ | 原力计划
本文插图
若此时next[j] == len(粉色部分)那么S1==S2 ， 又因为next[i] == next[j] ， 所以S1==S3 且 S3 == S4 ， 则可以推出S1 == S4 ， 这样我们就利用前面所获得的信息 ， 推出了S1 == S4这个信息 ， 然后将J移动到S1后一格 ， 只要再次比较patter[i] 与 patter[j]的相等情况 ， 就可以得出next[i+1]的值 。 这里因为i始终向后移动 ， 所以也是线性时间复杂度的算法 。ohhhhhhhhh～ 到这里 ， 大家就明白了为啥KMP算法的时间复杂度是M+N M+NM+N了 。KMP匹配字符串的完整代码附上！class KMP: def __init__(self, ss: str) -> list: self.length = len(ss) self.next_lst = [0 for _ in range(self.length)] self.next_lst[0] = -1 i = 0 j = -1 while i < self.length - 1: if j == -1 or ss[i] == ss[j]: i += 1 j += 1 self.next_lst[i] = j else: j = self.next_lst[j] self.pattern = ssdef match_str(self, ss:str): ans_lst =j = 0 for i in range(len(ss)): if ss[i] != self.pattern[j]: j = self.next_lst[j] if self.next_lst[j] != -1 else 0 if ss[i] == self.pattern[j]:if j == self.length: return i + 1 - self.length return -1tmp_kmp = KMP('iabc')print(tmp_kmp.match_str('adosjfoiajsoifjasiofjoiasdjoiabc'))版权声明：本文为CSDN博主「落阳学编程」的原创文章 ， 遵循CC 4.0 BY-SA版权协议 ， 转载请附上原文出处链接及本声明 。原文链接： https://blog.csdn.net/luoyangIT/java/article/details/106041160
【CSDN开玩笑呢？学习KMP算法能改变自我认知？ | 原力计划】
你点的每个“在看” ， 我都认真当成了喜欢


推荐阅读


上一篇：钛媒体薇娅李佳琦拍了拍“618”

下一篇：字节跳动在澳大利亚设办公室 由前谷歌高管担任总经理