4.2.2 KMP：失败时复用已经匹配的前后缀

朴素算法失败后丢掉已匹配信息。KMP 的关键是：若模式前缀 P[0..j-1] 已匹配，而 P[j] 失败，就把 j 回退到这段已匹配前缀的“最长真前缀且同时为后缀”的长度，主串下标不回退。

用 0 基前缀函数 pi[i] 表示 P[0..i] 的最长相等真前后缀长度：

vector<int> prefix(const string&p){
 vector<int> pi(p.size());
 for(size_t i=1;i<p.size();++i){
  int j=pi[i-1];
  while(j>0&&p[i]!=p[j])j=pi[j-1];
  if(p[i]==p[j])++j;
  pi[i]=j;
 }
 return pi;
}

模式 ababaca 的 pi 为 [0,0,1,2,3,0,1]。以位置 4 为例，前缀 ababa 的最长相等真前后缀是 aba，长度 3。

匹配时维护已匹配长度 j。当前字符失败就按 j=pi[j-1] 连续回退；相等则 j++；j==m 时找到起点 i-m+1。若要继续找重叠匹配，记录答案后令 j=pi[j-1]。

手工推演 T='abababaca'、P='ababaca'：前 5 个字符匹配到 ababa，主串下一字符 b 与模式 c 失败；j 从 5 回退到 pi[4]=3，无需重查主串前面的字符，随后可继续匹配并找到起点 2。

构造前缀表 $O(m)$，扫描主串 $O(n)$，总时间 $O(n+m)$、空间 $O(m)$。虽然 while 看似嵌套，j 的增减总量受线性界约束。

错解反馈：把“前缀”包含整个串会导致失败时不缩短；直接令 j=0 虽可能正确却退化；混用教材 1 基 next 与 0 基 pi 公式会整体错位。

迁移题：求模式 aabaaab 的 pi。答案 [0,1,0,1,2,2,3]。独立验收：每一位都能写出候选真前后缀，而不是只背表。