当前位置：首页 > news >正文

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

news 2026/5/12 8:19:02

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

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

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

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

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

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

KMP 的执行流程

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

预处理模式串：计算P的前缀函数数组prefix：
- P = A B C A B D
- prefix = [0,0,0,1,2,0]（比如P[4]对应的子串"ABCAB"，最长相等前后缀是"AB"，长度 2）。
匹配主串和模式串：
- 用两个指针i（主串）、j（模式串）遍历：
  - 若S[i] == P[j]：i++、j++；即当前字符匹配成功，两个指针一起往后挪，继续检查下一个字符
  - 若不相等：j = prefix[j-1]（利用前缀函数回退模式串指针，主串i不回退）；
  - 当j == 模式串长度：匹配成功，返回i-j（模式串在主串中的起始位置）。
具体解析一下

步骤 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）