KMP算法

基础概念

• 去看OI_wiki 前缀函数与 KMP 算法 - OI Wiki

关键理解

• 第二优化——关于为什么可以反复跳转

  

  1. 首先明确每次跳转到pi[i]实际含义是跳到从0开始长度的为j的串，从j+1开始匹配
  2. pi[i]维护了每次对应的最长前缀，也就是从i-j+1到i的最长后缀，如果跳转之后匹配失败，那么第二长度肯定是这个后缀的子集，同时满足最大的长度
  3. 也就是说，下一次的跳转目标也应该是前缀的前缀，也就是前缀的前缀函数，而且要求最大
  4. 那前缀长度是多少呢？pi[i]，前缀的最后一个索引是什么呢？pi[i]-1，那最大的前缀的前缀函数值是多少呢？维护在pi中，也就是pi[pi[i]-1]

• 代码思路

  • 对于ne数组的查找
    1. 首先明确找不到就跳到ne[j]
    2. 找到了意味着可以匹配下一位 j ++
    3. 找到了意味着 ne[i] = j
  • 对于字符串的查找
    1. 找不到跳到已经维护好的数组
    2. 找到了意味着可以匹配下一位 j ++
    3. 看一下是否找到最后一位了，如果找到就跳到上一个匹配的位置继续找 j = ne[j]