字符串匹配，KMP算法动画演示，帮助你了解KMP为自己写一个暴力匹配算法的得意体验。现在想想，真是惭愧，于是埋头学习KMP算法。为了不至于这么快忘记，希望小伙伴们能从我的理解中有所收获！文章附有精心制作的动画，便于理解。先分析一下暴力算法，为鲜花的诞生献上绿叶！下文中将待匹配字符串（长段）称为待匹配字符串，将待匹配字符串（短段）称为模式串。暴力匹配算法的思路很简单，就是每次先将待匹配字符串的首字母与模式串对齐，然后比较是否相同，如果相同，继续比较两个字符串的下一个位置，如果不是，则将模式字符串向右移动一位，然后重新从头开始匹配，如下图????从上面的动图，我们可以直观的看出下面的pattern字符串在匹配失败后只会移动一个空格，傻傻的，这导致它的时间复杂度是$M*N$，其中M是pattern字符串的长度，N是要匹配的字符串的长度。对于这个时间复杂度，我并不满意！对我明朗睿智的气质来说太傻了！那我们分析一下为什么这么傻。我们可以看到，当第一个匹配失败时，我们肯定希望它至少向右移动两个空格，因为模式字符串的第一个和第三个框都是a，既然第三个框已经匹配成功，那么就匹配第一个方格到第三个匹配位置无疑是成功的。我们的算法应该知道并利用这一点！但事实并非如此，这太愚蠢了。嗯，这样一来，貌似应该往动态规划的方向改（即利用已有的信息，方便下一步）。PS：80%以上的字符串问题都可以使用动态规划的思想来实现更低的时间复杂度。我们大多数人都听过一句老话：一个人最重要的是要有自知之明。同时，我们也一定听过别人说过：一个人只有对自己有了深刻的认识，才能找准自己的位置，快速的朝着目标前进！这两句话用在KMP算法上再合适不过了！KMP算法的核心在于模式串对自身的自我意识！想想我们是如何看待自己的：男，19岁，阳光帅气，聪明伶俐，这些自我认知都储存在我的脑海里。那么，模式串对自身的感知应该存储在哪里呢？是的，它在下一个数组中！字符串没有大脑，因此它需要额外的空间来存储它对自身的了解，并利用这些信息进行高效准确的判断。那么弦是如何感知自己的呢？其实很好理解，就是知道自己身体的哪些部位是相同的，这样在匹配失败后可以快速找到下一次的起点。这里是不是有点模糊？图片在这里！以上是KMP算法的动画。如果觉得动画有点快，可以多看几遍。在这个动画中，我并没有放出下阵的部分，而是以拟人化的方式展现出来。希望大家能理解为什么第一次匹配失败可以直接移动两个空格。就是因为模式串中第三种情况下的a，它知道第一种情况下有和自己相同的字符，并将这个信息告诉下一种情况下的字符，这样就可以直接移动a在第一种情况下，它就是那个位置。为了方便大家理解，我只放出了一个字符相同的情况。不妨扩展思考一下。如果第一种和第三种形式中的a不是字符而是字符串怎么办？如何？有点过头了？图片在这里！我们来看看模式串及其对应的下一个自知数组。i0123456next-1000123stringabcabcd不关心为什么下一个数组的第一项是-1。这个是为了写代码方便，所以暂且设为0。就是告诉下一个字符，如果匹配不上，就直接移动，同时下一个字符对应的next数组的值为0，当下一个字符匹配不上时，移动长度patternstring-匹配失败对应的字符下一个值长度。从第四个字符（i=3）开始，他们不断地告诉下一个字符：“将i=0移动到i=3的位置”，这句话是为i=4的字符移动4-1格，对于字符i=5，它移动5-2格，对于字符i=6，它移动6-3格：后面的减数恰好是这个字符对应的下一个数组的值！因为模式字符串知道自己够了，匹配失败时不需要回退，也不需要每次只移动一个空格，而是和待匹配的字符串一起移动。指向待匹配字符串的指针永远不会后退，并以线速度逐级向前移动。最后：KMP算法的时间复杂度是$M+N$这里不禁感叹！原来认识自己真的那么重要！下一步是找到给定模式字符串的下一个数组：python3代码在这里????defget_next_lst(ss:str)->list:length=len(ss)next_lst=[0for_inrange(length)]next_lst[0]=-1i=0j=-1whilei
