gjk算法python（pythonkmp算法）



参考：代码随想录

KMP的主要思想:
  当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

最长公共前后缀:
文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

为啥要把模式串（要匹配的串）逐个算出 最长公共前后缀 ：
因为你也不知道你匹配到哪就不能匹配了，将所有的情况列出来，然后哪里不能匹配直接对着表重新再弄。

初始化：
定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。

然后还要对next数组进行初始化赋值，如下：

处理前后缀相同的情况
如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。
代码如下：

处理前后缀不相同的情况
如果 s[i] 与 s[j+1]不相同，也就是遇到 前后缀末尾不相同的情况，就要向前回退。

回退必须j>=0,如果不是就代表无需回退。

next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。

那么 s[i] 与 s[j+1] 不相同，就要找 j+1前一个元素在next数组里的值（就是next[j]）。

错误解析：
“aabaaac”
aab 对应 aaa出问题了，所以用next数组回退，推到i=1，此时s[i]==s[j]，但是下面的代码却没有处理next[j]的情况

测试例题：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/pythonbc/43287.html