594. strStr II

way 2, KMP, suffix prefix. 利用重合前后缀的匹配原理,降低查找次数.

数据结构:
suffix array: 简称 A.
source string: 简称 s.
pattern / target string: 简称 p.
size: 前后缀重合长度.

. 准备 suffix array,
标记和前缀相同的后缀,记录每个 位置 i 结尾的后缀与前缀的重复字符的长度.
. 利用 suffix array, 省略不可能匹配的查找,
遇到不匹配时，只用从 已经匹配子串 与后缀相同的前缀尾部开始匹配查找.
如果没有 前后缀相同部分, pattern 从零开始.

s = "a.a.^^a.a.b-a.a.a.a.bxa__bb"
p = "a.a.b-a.a.a.a.bxa"

a .a .^^a.a.b-a.a.a.a.bxa__bb
012345..

a.a.^ 与 a.a.-, a.a. 相同, ^ - 不同.
基于已经匹配的子串 a.a. 的重合前后缀, 是 a. ,
在 i 前一个字符结尾, 它的后缀与前缀相同部分是 a., 前后缀重合长度 = 2,
j = 2, 即第三个位置.
我们可以从第三个位置开始新一轮匹配, 即 source index = 4, pattern index = 2.
a.? == a.?, source v.s. pattern.
我们就不需要从 source index = 1 ( 0 的下一个) 开始从头匹配 pattern,
 - 根据 suffix array, 我们知道前面没有重合部分.
也不需要从 pattern index = 0 ( source index = 2) 开始匹配 pattern,
 - 因为已知前两个字符(a.)是前后缀重合. 只需要看看下一个字符是否相同.

封装, build_suffix_array(p): 返回数组, 元素值是每个位置后缀与前缀重复的长度.
构造方法和字符串查找方法类似.

初始化, 前缀索引 j = 0, 后缀索引 i = 0.
比较前缀和后缀当前字符:
如果相同, 长度值加一, A[i] = j + 1, 即在前一个字符后缀重合长度基础上加一, 前后缀指针各自加一.
如果不同,
- 如果 j > 0: j = A[j - 1], 更新前缀指针, 从已经匹配的子串 的 (最长)前后缀相同的前缀尾部开始匹配;
  . i.e. "a.a." 的重合前后缀是 "a.", (最长)重合前后缀, 是一个 更短的子串.
- 如果 j == 0: 没有重复前后缀, A[i] = 0; i += 1, 源字符串的起始查找位置,前进一位.

 a  .   a  .  b   -  a  .   a   .   a   .  a  .   b  x  a  # 忽略空格. 加空格为了上下位置对应.
[0, 0, 1, 2, 0, 0, 1, 2, 3, 4, 3, 4, 3, 4, 5, 0, 1] # suffix array.
 0  1  2  3  4  5  6  7  8  9  10 ..

例子:
a 和 a.a.b-a 前缀是 a 后缀是 a , 前后缀重合长度是 1,
a. 和 a.a.b-a. ,  后缀是 a. , 前后缀重合长度是 2,
..
a.a. 和 a.a.b-a.a. 前缀是 a.a. 后缀是 a.a. , 前后缀重合长度是 4,
a.a.b 和 a.a.b-a.a.a , 后缀结尾字符 a 和前缀尾 b 不同.
之前字符 . 的前后缀重合长度是 4,
j = A[j - 1] = A[4 - 1] = 2, 即用 p[2] 匹配 s[i]
如果还是不匹配, j = A[j - 1] 迭代计算, 直到 j == 0.

i, j = 1, 0
while i < n:
    if p[i] == p[j]:
        A[i] = j + 1 # A[i] = A[i - 1] + 1; 和 j + 1 一样的效果.
        j += 1
        i += 1
    else:
        if j > 0:
            j = A[j - 1]
        else:
            A[i] = 0
            i += 1
return A
.

class Solution:
    """
    """
    def strStr2(self, s, p):
        if p is None or s is None:
            return -1
        if p == "":
            return 0
        A = self.suffix(p)
        n = len(s)
        i, j = 0, 0
        ans, t = -1, 0
        while i < n:
            # t += 1
            if s[i] == p[j]:
                if j == len(p) - 1:
                    ans = i - j
                    break
                j += 1
                i += 1
            else:
                if j > 0:
                    j = A[j - 1]
                else:
                    i += 1
        # print(f"time:  {t}, n {n}")
        return ans

    def suffix(self, p):
        n = len(p)
        A = [0] * n
        i, j = 1, 0
        while i < n:
            if p[i] == p[j]:
                A[i] = j + 1
                j += 1
                i += 1
            else:
                if j > 0:
                    # print(j, A[j - 1], p[j], p[A[j - 1]])
                    j = A[j - 1]
                else:
                    A[i] = 0
                    i += 1
        return A