Problem J24: Substring Match / 串匹配问题

版权信息： JLOJ2353 · 字符串基础 · KMP算法入门

---

** 任务总览**

任务名称	时间限制	内存限制	分数
串匹配问题	1 sec	1024 MB	15 points

---

题目描述

给定两个字符串：

• 字符串 ​ a ​（称为“主串”）；
• 字符串 ​ b ​（称为“模式串”）；

请你判断：​ 模式串 b 是否在主串 a 中出现过 ​。

若出现，输出第一次出现的位置（从 1 开始）；若未出现，输出 -1。

---

输入格式

输入共两行：

1. 第一行为主串 $a$；
2. 第二行为模式串 $b$。

字符串均为小写英文字母，长度 $< 5000$。

---

输出格式

输出一个整数，表示：

• 若匹配成功，输出模式串第一次出现的位置（从 1 开始计数）；
• 若匹配失败，输出 -1。

---

输入输出样例

输入示例

asdfgh
dfg

输出示例

3

---

题目分析与解法

这是经典的​ 字符串匹配问题 ​，可用以下两种方法解决：

✅ 方法一：朴素枚举匹配

从主串的每个起始位置逐个字符尝试匹配模式串，时间复杂度 $O(n \cdot m)$。

✅ 方法二：KMP 算法（推荐）

通过构造 next 数组 实现高效跳跃，时间复杂度 $O(n + m)$。

---

KMP 算法核心思路

*用 next[j] 表示模式串前缀 b[0..j - 1] 的最长相等前后缀长度；

• 在匹配过程中，遇到失配时跳回 next[j] 继续比较，不必回溯主串。

✅ next 数组构造规则：

1. 初始化：next[0] = -1；
2. 若 b[j] == b[k]，则 next[j + 1] = k + 1；
3. 若不相等，则回溯到 next[k]，重复尝试直到匹配或 k = -1。

---

时间复杂度分析

步骤	复杂度
构建 next 数组	$O(m)$
字符串匹配过程	$O(n)$
总复杂度	$O(n + m)$

---