📝 KMP数组

KMP算法的基本思想

1. 利用已有的匹配信息：
• 当在主字符串中进行匹配时，如果遇到不匹配的字符，KMP算法不会简单地将模式字符串向右移动一位重新开始匹配。而是利用之前已经匹配过的部分，根据部分匹配表（前缀函数）的信息，确定下一个可能的匹配位置，从而减少比较次数。

2. 前缀函数（部分匹配表）：
• 前缀函数用于记录模式字符串中每个位置之前（不包括当前位置）的最长相等的真前缀和真后缀的长度。
• 通过前缀函数，KMP算法能够知道在发生不匹配时，模式字符串应该向右移动多少位，以便继续进行有效的匹配。

🤗 实现过程

• 先看看代码吧

1. 初始化：
• pos = 0：表示当前没有任何前缀和后缀匹配。
• 通常，kmp 数组会初始化为全零数组，表示所有位置初始的最长前缀后缀长度为0。

2. 遍历模式串：
• for i in range(2, n + 1)：从模式串的第2个字符开始遍历到第n个字符。这里假设字符串索引从1开始。
• 每次迭代，i 表示当前正在处理的字符位置。

3. 处理当前位置的字符：
• 比较当前字符与前缀字符：
• s[pos + 1]：当前前缀的下一个字符，即尝试扩展前缀。
• s[i]：当前处理的位置字符。

4. 处理不匹配情况：
• while pos and s[pos + 1] != s[i]：
• 当 pos > 0 且当前字符不匹配前缀的下一个字符时，需要回退到前缀的最长前缀后缀位置，避免重复比较。
• pos = kmp[pos]：将 pos 更新为前缀的最长前缀后缀长度，即跳转到 kmp[pos]。

5. 处理匹配情况：
• if s[pos + 1] == s[i]：
• 如果当前字符与前缀的下一个字符匹配，则可以扩展当前的前缀后缀长度。
• pos += 1：增加前缀后缀的长度。
• kmp[i] = pos：记录当前 i 位置的最长前缀后缀长度。

四、示例解析

1. 初始化：
• pos = 0
• kmp = [0] * (n + 1) → kmp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

2. i = 2：
• 比较 s[1] (A) 和 s[2] (B) → 不匹配。
• pos = 0
• kmp[2] = 0

3. i = 3：
• 比较 s[1] (A) 和 s[3] (A) → 匹配。
• pos = 0 + 1 = 1
• kmp[3] = 1

4. i = 4：
• 比较 s[2] (B) 和 s[4] (B) → 匹配。
• pos = 1 + 1 = 2
• kmp[4] = 2

5. i = 5：
• 比较 s[3] (A) 和 s[5] (C) → 不匹配。
• 回退：pos = kmp[2] = 0
• 比较 s[1] (A) 和 s[5] (C) → 不匹配。
• kmp[5] = 0

6. i = 6：
• 比较 s[1] (A) 和 s[6] (A) → 匹配。 → s[1]回到开头了
• pos = 0 + 1 = 1
• kmp[6] = 1

7. i = 7：
• 比较 s[2] (B) 和 s[7] (B) → 匹配。
• pos = 1 + 1 = 2
• kmp[7] = 2

8. i = 8：
• 比较 s[3] (A) 和 s[8] (A) → 匹配。
• pos = 2 + 1 = 3
• kmp[8] = 3

9. i = 9：
• 比较 s[4] (B) 和 s[9] (B) → 匹配。
• pos = 3 + 1 = 4
• kmp[9] = 4

📎 参考文章