Python版算法复习笔记（四）：字符串/KMP算法

在该章收获的重要知识点是KMP算法。

应用场景：主要用于字符串的匹配上：字符串a是否为字符串b的子串
基本思想：在匹配过程中，当出现字符串不匹配时，可以记录一部分之前已经匹配的字符串内容，利用这些信息避免从头开始匹配。
重点：如何记录已经匹配的文本内容。

下面介绍如何实现KMP算法，涉及到两个名词：前缀表，next数组。这两个名词其实是一种东西的两种不同的表现形式，区别很小，核心就是前缀表。

什么是前缀表：
对于字符串a，记录下标i之前（包括i）的字符串中，有多大长度的相同前后缀。

前缀：从第一个字母开始向后延申，任意长度，不包含最后一个字母
后缀：从最后一个字母向前延申，任意长度，不包括第一个字母
eg：
abcde包含的前缀有a, ab, abc, abcd
abcde包含的后缀有e, de, cde, bcde
最长相等前后缀：字符串的前后缀中，长度最大的相等的前缀和后缀
eg:
abcba的最长相等前后缀为1，即a
abcab的最长相等前后缀为2，即ab

前缀表怎么用：
用于回退，记录了字符串a与字符串b不匹配的时候，字符串a应该从哪里开始重新匹配。 怎么创建前缀表

① 列出字符串a的所有从0位置开始的子串

eg: abcab可得：
a
ab
abc
abca
abcab

② 统计各子串的最长相等前后缀

最长相等前后缀 子串
0 a ( 无前后缀 )
0 ab ( 前缀：a ；后缀：b )
0 abc ( 前缀：a ab ；后缀：c bc )
1 abca ( 前缀：a ab abc ；后缀：a ca bca )
2 abcab ( 前缀：a ab abc abca ；后缀：b ab cab bcab )

③ 得到前缀表
[ 0, 0, 0, 1, 2 ]

④ 由前缀表获得next数组
去除前缀表的最后一个数字，并在0位置插入-1：
[ -1, 0, 0, 0, 1 ]

对于字符串abcab
已知m：abca的最长相等前后缀为1，即a，如果后面新增一个字母b==m[1]，则新字符串的最长相等前后缀为1+1，否则，需要重新计算该字符串的最长相等前后缀。

① 创建前缀表，得到next数组
② 同时从index 0遍历字符串a和字符串b，当不匹配时，让字符串a指定index，移动到当前位置与字符串b对齐

eg. 字符串a: aaab，字符串b: aaacaaab
得到前缀表：[ 0, 1, 2, 0 ]
得到next数组：[ -1, 0, 1, 2 ]
两个独立的索引index1，index2 分别从字符串a和字符串b的0位置出发，开始匹配
在 index1 == index2 == 3 的位置字符串a和字符串b不匹配，
a a a c a a a b
a a a b
查询字符串a在 index1 3 位置的next数组上的值，
将a[2]移动到当前位置,
a a a c a a a b
  a a a b
继续比较字符串b的index2 3 和字符串a的index1 2，不匹配，
查询字符串a在 index1 2 位置的next数组上的值，
将a[1]移动到当前位置，
a a a c a a a b
    a a a b
继续比较字符串b的index2 3 和字符串a的index1 1，不匹配，
查询字符串a在 index1 1 位置的next数组上的值，
将a[0]移动到当前位置，
a a a c a a a b
      a a a b
继续比较字符串b的index2 3 和字符串a的index1 0，不匹配，
查询字符串a在 index1 0 位置的next数组上的值，
此时next数组上对应的值为-1，则假想字符串a前面有一个空格，将-1位置的空格与字符串b的index2 3 对齐
(index1 = index2 + 1, index2 += 1 )
a a a c a a a b
        a a a b
继续逐一匹配，直到匹配成功

目前对于KMP算法的理解不够深入，尤其是快速创建next数组的代码，后序需加深理解。