CSDN|开玩笑呢？学习KMP算法能改变自我认知？

本文插图
已知蓝色区域相等且长度都为len ，那么很明显， next[i] == len ，若此时模式串pattern[i] != pattern[j]（两个灰色区域不相等）。那么看下图：
本文插图
若此时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算法能改变自我认知？ | 原力计划( 二 )

推荐阅读

数字财经智库科技这5类首当其冲，失业真的要来？马云曾发预警：50%工作被替代

『地中海』六大主流风格庭院设计，植物配置，配图，详解

『游戏湿太』Clearlove：打得不好的时候会阴阳怪气他们，EDG赛后群访

张兰|张兰骨头疼仍直播，满头白发显沧桑，曾揭密大S刷卡失败原因

你觉得把啥东西的logo遮起来，那东西看起来还不错

新华网|提升出行感受，第三届进博会交通保障更优化

俯卧撑|女子花48000元做了改善胸部下垂手术，发现效果与医院承诺的相差甚远

浅浅说科技|搭载65W超级快充，还解决5G手机的通病，充电第一的5G手机诞生

红茶的饮用与保存方法,红茶调饮法每克茶

21财闻汇iPhone12真要来了？但苹果还是一夜蒸发了3800亿元

玫瑰花茶的泡法解析视频玫瑰花茶的泡法解析

中国新闻网|淮河发生2020年第1号洪水水利部全力做好应对工作

伊隆·马斯克|世界首富马斯克开始裁员，地主家的余粮也不多了？

精神病患者能活多久(精神病老是不停乱说话怎么办)

Canalys数据显示：vivo稳居Q2中国智能手机市场第二

修饰|街拍:身材玲珑有致的小姐姐,无需过多的修饰就可以展现你的魅力

滇红茶怎么分等级的？

晶用军事|激光武器怎样才能击落导弹和运载火箭？

应试教育@富人的教育，穷人玩不起，平民子弟只有认真备战高考才是王道

家人|大雪后，家人迷上这早餐，5分钟蒸一锅，营养好消化，解馋又顶饱