LeetCode 补充题 106. 字符串模式匹配计数
题目描述
[!green]
牛客原题： ✅ 补充题 106. 字符串模式匹配计数
给你文本字符串
T和非空模式字符串S，返回S在T中出现的次数。不同起始位置分别计数，允许匹配区间相互重叠。
示例 1：
输入：
T = "aaaa", S = "aa"
输出：3
解释： 匹配起点为 0、1、2，允许不同匹配区间重叠。
示例 2：
输入：
T = "abababa", S = "aba"
输出：3
解释： 匹配起点为 0、2、4。
提示：
1 <= len(S) <= 5000001 <= len(T) <= 1000000
题意分析
每个合法起点都要统计，即使它与前一次命中的区间重叠。逐个起点重新比较可能反复扫描同一段文本，在当前长度上限下需要利用已经匹配的内容减少比较。
KMP 保存模式串自身的前后缀关系。失配后只调整已匹配长度，文本位置不用倒退；完整命中后也用同一关系保留可复用的后缀。
解法：KMP 完整命中后继续回退匹配
核心思路
[!blue]
pi[i]表示模式前缀pattern[0..i]的最长相等真前缀、真后缀长度；“真”表示不能取整个区间。构造时，若下一个字符不能延长匹配，就令j = pi[j - 1]，尝试更短且仍可能成立的前后缀。扫描文本时，
j表示当前文本后缀与模式前缀相等的长度。字符相等就把j加 1；失配则沿pi回退，直到能接上当前字符或j变成 0。被跳过的长度不满足前后缀关系，不可能构成有效匹配。当
j == m时，恰好发现一个以当前位置结尾的完整匹配，计数加 1，再令j = pi[m - 1]。保留这段后缀才能继续发现重叠命中，同时每个结尾只计一次。回退后j < m，下一次读取模式字符也不会越界。
解题步骤
- 构造模式串的前缀函数。
- 扫描文本，失配时沿前缀函数回退。
- 完整匹配后计数，再回退到最长真前后缀继续匹配。
代码实现
class Solution {
public int countMatches(String text, String pattern) {
int m = pattern.length();
if (m == 0) {
throw new IllegalArgumentException("pattern must not be empty");
}
int[] pi = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
pi[i] = j;
}
int answer = 0;
int j = 0;
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == m) {
answer++;
j = pi[j - 1];
}
}
return answer;
}
}
func countMatches(text, pattern string) int {
m := len(pattern)
if m == 0 {
panic("pattern must not be empty")
}
pi := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && pattern[i] != pattern[j] {
j = pi[j-1]
}
if pattern[i] == pattern[j] {
j++
}
pi[i] = j
}
answer, j := 0, 0
for i := 0; i < len(text); i++ {
for j > 0 && text[i] != pattern[j] {
j = pi[j-1]
}
if text[i] == pattern[j] {
j++
}
if j == m {
answer++
j = pi[j-1]
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(\lvert T\rvert+\lvert S\rvert)$。
- 空间复杂度：额外空间 $O(\lvert S\rvert)$。
关键点总结
[!green]
pi描述模式自身的结构，扫描状态j描述当前文本与模式的匹配长度。- 完整命中后的回退与失配回退共用前后缀关系，不能把
j直接清零。- 每次前进最多让
j增加 1，回退只使其减小，因此总比较次数为线性量级。
易错点总结
[!yellow]
完整匹配后不能直接返回，也不能把j清零；非空模式是题目约束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 28. 找出字符串中第一个匹配项的下标 | 简单 | 原题首次命中即可返回，本题计数后必须继续扫描，并保留可重用的前后缀。 |
| 459. 重复的子字符串 | 简单 | 同样利用最长真前后缀信息，原题据此识别周期，本题用它支持重叠匹配。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！