数据结构总结-字符串:kmp
CouriourC Lv5
  2022-10-24 15:08:39 2022-10-24 15:08    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_next(t):
    next_list = [-1] * len(t)
    j = -1
    i = 0
    s = t
    while i < len(s):
        if j == -1 or s[i] == t[j]:
            i += 1
            j += 1
            next_list[i] = j
        else:
            j = next_list[j]
    return next_list

get_next('abababc')

对于 Kmp 算法中书上的 next数组求法一直处于一个 懵逼 的状态。不理解为什么有 -1，为什么求前后公共后缀不需要用到单独的 check 机制，毕竟我们人眼来看都会去反复的判断（至少我之前一直都是）。

  • 思想归类

    • 滑动窗口

      • 我们求最大前后缀，依赖与前面的值所已经有的最长前后缀，从而不需要再，然后以此向前推

      • 回忆一下之前做的习题：无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在我们这里用的是一端不动的窗口

  • 动态规划的角度思考

代码中的求解过程

举个例子: abababa，我们在运行求第 6 个的时候: a b a b a "b" a，我们之前所求到的前面的公共前后缀的长度也就是 3 aba

前后缀是包括我们的第一个的，所以我们只需要每次从 aba的后面开始判断, aba "?"，这个 ? 和我当前的对应到的也就是第 7 个的结果,这个取决于当前浏览的 i 也就是 "b" 是否满足等于之前所找到的最长的,如果不是就向下找前一段所求的公共最长子串,同样的道理也是取决于这个公共前后缀的尾巴与我现在所在的这个后缀的尾巴是否相等
a b a b a "b" a
0 1 1 2 3 4 5

a 0: 默认值

b 1: 前面的最长公共子串为 0 ,至于为什么要 +1 是因为我们当前匹配的时候,前面的已经发现在这个位置就不对,那 a 就没必要再与 b 这个位置比较,所以就跳到 b 的后面去,也就是 j 从头再开始。

需要注意的是,我们求 这个值的时候,i 在 我们当前正在求的前一个位置,在这个满足后设置的才是我们当前求得这个 也即是说我们如果从 j = 0 开始的时候,也就是错开了一个位置
得到的 next_list = ["0" 0 1 1 2 3 4 5]
而不是next_list = [ 0 1 1 2 3 4 5]

a 2: 前面的前缀之前我们发现从 第 0 的位置是不存在前后缀的,然后现在我们要观察的是 前面的公共前后缀,也就是 ab 的公共前后缀, a 与 我当前的 b 并不相等,

b 3: OK,基于以上的，我们到求第三的这个位置,这个位置的判定条件就是:我们前面的 aba所求到的这个的最长公共前后缀的最后一个 ab? 中的 ?与我当前的 a是否相等(需要留意,用程序求的时候,是看前面的前面与我当前的位置的情况,然后推到后面的情况

对于我们的直觉求法就是直接瞪眼神功对于上面的 求 i+1 = 3(这时候 i是等于 2) 也就是求第 4**(经历了 i= i +1-> next_list[3])** 这一个字符前面的公共前后缀的时候(j = -1的时候求到的 next_list是正常的匹配顺序,也就是 i是从正常的 0开始的其前面的字符是 aba来看 ,之前我们发现最长公共前后缀就是 0 也就是 a这个时候我们判断 t[2]:a是否等于(后缀和这个前面的最长的前缀的最后一个元素做比较)然后发现 a = a 是相等的,然后就可以得到 2 了而不是还要去扫描后面的,因为我们这一次扫描带来的元素只有一个,有一种滑动窗口的味道了。

再重新整理一下：

  • 窗口中的进入了一个元素
  • 这个元素对窗口产生的影响

一些问题：这种避免回溯的方法，能否在窗口中合理的利用呢。

还得继续做题，💪

 评论