匹配回文串：利用KMP算法求解

一、先明确问题：什么是 “回文串”？

回文串定义：回文串是指正读和反读都完全相同的字符串

比如 “abcba”“aaa”“level” 都是回文串，而 “abcd”“abbaa” 不是。可以简单理解为：字符串从左到右读，和从右到左读，得到的结果完全一致。

二、了解算法：什么是KMP算法？

KMP 算法是一种高效的字符串匹配算法，全称为 Knuth-Morris-Pratt 算法，核心作用是在主串中快速找到模式串的出现位置，时间复杂度优化到了线性(O(n+m)，n是主串长度，m是模式串长度），比暴力匹配的O(n*m)高效得多。

KMP 的核心是利用 “模式串自身的前后缀信息”，避免不必要的回退——匹配失败时，主串指针不回退，只调整模式串指针的位置。

KMP 的执行流程

以 “主串S = "ABCABCABD"，模式串P = "ABCABD"” 为例：

1. 预处理模式串：计算P的前缀函数数组prefix：

   • P = A B C A B D
   • prefix = [0,0,0,1,2,0]（比如P[4]对应的子串"ABCAB"，最长相等前后缀是"AB"，长度 2）。

2. 匹配主串和模式串：

   • 用两个指针i（主串）、j（模式串）遍历：
     • 若S[i] == P[j]：i++、j++；即当前字符匹配成功，两个指针一起往后挪，继续检查下一个字符
     • 若不相等：j = prefix[j-1]（利用前缀函数回退模式串指针，主串i不回退）；
     • 当j == 模式串长度：匹配成功，返回i-j（模式串在主串中的起始位置）。
3. 具体解析一下

步骤 1：S [0] == P [0]（A == A）

• 匹配成功 → i++（i=1），j++（j=1）

• 当前状态：i=1，j=1

步骤 2：S [1] == P [1]（B == B）

• 匹配成功 → i++（i=2），j++（j=2）

• 当前状态：i=2，j=2

.............

步骤 6：S [5] != P [5]（C != D）

• 匹配失败！按规则：j = prefix [j-1]（j 现在是 5，j-1=4，prefix [4] = 2）
• 所以 j 回退到 2，i 保持 5 不变（主串不回退）
• 当前状态：i=5，j=2

注：为什么回退到 j=2？

当步骤 5 后 j=5（P [5] = D），S [5] = C，匹配失败时：

• j-1 = 4 → prefix [4] = 2 → 意味着 P [0..4]（"ABCAB"）的最长相等前后缀是 "AB"（长度 2）
• 所以不用让 j 回退到 0，而是直接回退到 2（前缀 "AB" 的末尾），相当于复用了之前匹配成功的 "AB"，直接检查 P [2]（C）和 S [5]（C）即可

再通俗一点来讲，就是S [5] != P [5]（C != D）意味着第六个字母主串和子串不同，但是前面的我们都是相同的，既然现在不同了，我们就要回退回去（子串）再比较，那么退到哪里呢？我们就找子串的前缀和后缀最长相等的地方，主串的指针指的是ABCABCABD，子串的指针就要ABCABD退到C来和主串再比较。

步骤 7：S [5] == P [2]（C == C）

• 现在检查 S [5]（C）和 P [2]（C）→ 匹配成功
• 执行 i++（i=6），j++（j=3）
• 当前状态：i=6，j=3

步骤 8：S [6] == P [3]（A == A）

• 匹配成功 → i++（i=7），j++（j=4）
• 当前状态：i=7，j=4

.............

终止条件：j == 6（模式串长度）

• 匹配成功！返回「模式串在主串中的起始位置」= i - j = 9 - 6 = 3