sae网站代备案,wordpress增加文章目录,泰安人才,多媒体展厅KMP算法理解 最长公共前后缀next合并主子串子串偏移 参考b站#xff1a;子串偏移、合并主子串
最长公共前后缀next
这个概念是一个trick#xff0c;帮助我们记录遍历了一遍的数组的相似特性#xff0c;想出来确实很nb#xff0c;我也不理解逻辑是怎么想出来的。 字符串的… KMP算法理解 最长公共前后缀next合并主子串子串偏移 参考b站子串偏移、合并主子串
最长公共前后缀next
这个概念是一个trick帮助我们记录遍历了一遍的数组的相似特性想出来确实很nb我也不理解逻辑是怎么想出来的。 字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。 例如对于字符串 ababc
前缀有a, ab, aba, abab第一个字符一定会有后缀有c, bc, abc, babc最后一个字符一定会有
最长公共前后缀指某个字符串的前缀和后缀中相等的最长子串。例如
对于 abab最长公共前后缀是 ab长度为 2。对于 abc没有公共前后缀长度为 0。
例如对于模式串 ababc其前缀表为 [0, 0, 1, 2, 0]
第 0 位a没有前后缀值为 0。第 1 位ab没有公共前后缀值为 0。第 2 位aba最长公共前后缀为 a值为 1。第 3 位abab最长公共前后缀为 ab值为 2。第 4 位ababc没有公共前后缀值为 0。
现在我们希望在一次遍历字符串的过程中记录该字符串的相似性质该如何计算最长公共前后缀的数组通常被称为next用递推的性质 假设我们希望求next[i]并知道红色段next[i-1]len那说明[0,i-1]的子串的首尾均有长度为len的前后缀
如果str[i]str[len]说明[0,i]的子串的首尾均有len1长度的前后缀得到next[i] len1注意下标从0开始所以比较的是str[len] 如果str[i]!str[len]我们继续寻找[0,i-1]的子串中第二长、第三长的前缀串粉色段这些字符串虽然长度小于len但起点和终点依然是0和j-1因为next[i]找到的前后缀一定要经过0和j 把寻找的过程可以写成while目标是找到尽量长的粉色段n并满足str[n]str[i]现在问题是n怎么获得我们最初知道next[i-1]len所以绿色橙色而现在又找到了蓝色橙色所以有蓝色绿色所以粉色段恰恰可以用next[len-1]表示当找到了粉色段但不满足str[n]str[i]时继续找下一个粉色段即next[n-1]如此循环 最终可以得到next数组方法如下
vectorint pi(str.size());
for (int i 1; i str.size(); i) {int len pi[i-1];while (len ! 0 str[i] ! str[len]) {len pi[len - 1];}if (str[i] str[len]) {pi[i] len 1;}
}合并主子串
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。 把haystack 和 needle合并中间用#分隔求合并串的next数组如果数组中有值等于len(needle)则说明有匹配项 这种方法可以直接在next数组获得的过程中判断代码如下
class Solution:def strStr(self, haystack: str, needle: str) - int:n len(haystack) #主串的的长度m len(needle) #子串的长度if haystack needle: #因为i从1开始所以处理edge casereturn 0s needle # haystack #注意把子串放前面这样前缀和才能覆盖子串next [0] * len(s)for i in range(1, n m 1): #注意1是因为#多了一位len_ next[i - 1]while len_ ! 0 and s[i] ! s[len_]: #等于0也是没有会跳过的len_ next[len_ - 1]if s[i] s[len_]: #跳出循环要不是0要不相等next[i] len_ 1if next[i] m:#返回第一个return i - m*2 #合并串从第m1位开始才是主串所以主串中开始匹配的下标是i - (m1) - m 1i-2*mreturn -1子串偏移
KMP的主要思想是当出现字符串不匹配时可以知道一部分之前已经匹配的文本内容可以利用这些信息避免从头再去做匹配了。 子串偏移方法一句话就是利用子串的前后缀和保证下一个可能匹配的地方就是主串的后缀。
比如第i位AC虽然没有匹配上但我们知道[0,i-1]的内容是一样的如何复用这一信息注意i指的是子串指针这里图示主串和子串指针是一样的所以没有区分但本质要利用子串next数组的前后缀相同所以要用子串指针 为了和暴力方法区分我们不希望直接把主串的指针移到下一个位置开始遍历而是一直向前方移动这需要我们移动指针到仍然有可能重新匹配的地方如何寻找利用next数组和[0,i-1]的内容的已知信息[0,i-1]中的前后缀长度是next[i-1]而主串匹配子串最基本的要求就是从第一个字符相等。现在主串的头需要移动因为0作为起点不行了我们又不像只移动一个这时可以想到主串的后缀恰好等于子串的开头举个例子主串是ABCABDC子串是ABCABCi此时是5我们已知[0,4]的ABCAB相等和next[4]2。主串把0当起点时找不到匹配的但此时主串[0,4]的末尾和子串的开头相等都是AB所以把主串的起点移动到i-next[i-1]5-23后主串和子串又有了next[i-1]长度的相等段因为next数组的定义0-3之间不可能有另外等于子串开头的部分前后缀一定会覆盖到第一个可能的起点处如ABACAB匹配ABACAD时不可能把起点移到中间的A因为下一位是C前后缀在计算时就比较过了这样等价于主串不动还是从第i位开始比较而子串从则回退到next[i-1]位因为子串的[0,i-1)已知和主串是相等的回到图中的例子就是
这种方法的代码如下
class Solution:def getNext(self, next, s):for i in range(1, len(s)):len_ next[i - 1]while len_ ! 0 and s[i] ! s[len_]: #等于0也是没有会跳过的len_ next[len_ - 1]if s[i] s[len_]: #跳出循环要不是0要不相等next[i] len_ 1def strStr(self, haystack: str, needle: str) - int:next [0] * len(needle)self.getNext(next, needle)i 0 #主串指针j 0 #子串指针for i in range(len(haystack)):while j 0 and haystack[i] ! needle[j]:#不匹配子串到下一个可能匹配的地方next[j-1]注意只要j0要一直找而不是只试一次j next[j - 1]if haystack[i] needle[j]:#字符匹配指针后移j 1if j len(needle):#在主串中找到了子串return i - len(needle) 1return -1
