0028. Find the Index of the First Occurrence in a String¶
题目信息¶
- 题号:
找出字符串中第一个匹配项的下标
- 难度:
Easy
- 主题:
字符串、模式匹配、前缀函数、KMP
- 原题:
- 重点:
从逐起点重新匹配,推导到复用已匹配后缀,并用前缀函数在失配时跳过不可能起点
题目重述¶
给定字符串 haystack 和 needle,在 haystack 中寻找第一次出现的、与 needle 完全相同的连续
子串,并返回该子串的零基起始下标;若不存在这样的子串,返回 -1。
匹配必须覆盖 needle 的全部字符,且字符顺序和大小写都必须完全相同。若 needle 在文本中出现多次,
只返回起始下标最小的一次。两个字符串长度均位于 [1, 10^4],只包含小写英文字母。
自建示例¶
首位置命中:
haystack = "abracadabra"、needle = "abra",返回0;多次出现:
haystack = "mississippi"、needle = "issi",分别从下标1和4开始出现,返回1;需要复用前缀:
haystack = "abababaca"、needle = "ababaca",返回2;模式比文本长:
haystack = "abc"、needle = "abcd",返回-1;不存在:
haystack = "algorithm"、needle = "rhythm",返回-1。
C++ 实现¶
#include <string>
#include <vector>
class Solution {
private:
int naiveSearch(const std::string& text, const std::string& pattern) {
const int n = static_cast<int>(text.size());
const int m = static_cast<int>(pattern.size());
for (int start = 0; start + m <= n; ++start) {
int offset = 0;
while (offset < m && text[start + offset] == pattern[offset]) {
++offset;
}
if (offset == m) {
return start;
}
}
return -1;
}
std::vector<int> buildPrefix(const std::string& pattern) {
const int m = static_cast<int>(pattern.size());
std::vector<int> prefix(m, 0);
for (int index = 1; index < m; ++index) {
int matched = prefix[index - 1];
while (matched > 0 && pattern[index] != pattern[matched]) {
matched = prefix[matched - 1];
}
if (pattern[index] == pattern[matched]) {
++matched;
}
prefix[index] = matched;
}
return prefix;
}
int kmpSearch(const std::string& text, const std::string& pattern) {
const std::vector<int> prefix = buildPrefix(pattern);
int matched = 0;
for (int index = 0; index < static_cast<int>(text.size()); ++index) {
while (matched > 0 && text[index] != pattern[matched]) {
matched = prefix[matched - 1];
}
if (text[index] == pattern[matched]) {
++matched;
}
if (matched == static_cast<int>(pattern.size())) {
return index - matched + 1;
}
}
return -1;
}
public:
int strStr(std::string haystack, std::string needle) {
return kmpSearch(haystack, needle);
}
};
题解¶
逐起点验证¶
设文本长度为 n,模式长度为 m。一个完整匹配只能从 0 到 n - m 开始。最直接的方法是依次选择
每个合法起点 start,再从模式下标 0 开始逐字符比较。
naiveSearch 按起点递增顺序检查,因此第一次成功一定是最早出现位置。每个候选要么在某处失配,要么完成全部
m 次比较;所有合法起点都被覆盖,所以不会漏解。
问题在于,相邻起点之间可能重复比较相同字符。以 text = "abababaca"、pattern = "ababaca" 为例,
从起点 0 已经匹配 ababa 后,在下一字符处失配。若把模式完全移到起点 1 并从头开始,就丢弃了
已经确认的文本后缀信息。重复结构较强时,许多起点都会先匹配很长前缀再失配,最坏时间达到 O(nm)。
失配后的有效起点¶
假设当前已经连续匹配了模式前 matched 个字符:
文本已读后缀:pattern[0 .. matched)
下一文本字符与 pattern[matched] 失配时,不能继续保留完整的 matched 个字符。新的候选匹配若仍然利用
已经读过的文本,它的模式前缀必须等于这段已匹配文本的某个后缀。
而已匹配文本本身等于 pattern[0 .. matched),所以问题转化为:在这个模式前缀中,寻找一个同时也是后缀的
最长真前缀。若其长度为 fallback,则文本末尾 fallback 个字符已经等于
pattern[0 .. fallback),无需重新读取,可以继续尝试匹配 pattern[fallback]。
只考虑真前缀,是因为长度仍为 matched 的候选刚刚已经失配。寻找最长者则能保留最多已确认字符;若它仍然
失配,再继续尝试更短边界。
前缀函数¶
定义 prefix[index] 为模式子串 pattern[0 .. index] 的最长相等真前后缀长度。这里“前后缀相等”表示:
前缀从模式下标
0开始;后缀在下标
index结束;二者内容相同;
长度小于当前子串总长度。
例如模式 ababaca 的前缀函数为:
|
字符 |
当前子串 |
|
最长边界 |
|---|---|---|---|---|
0 |
|
|
0 |
空 |
1 |
|
|
0 |
空 |
2 |
|
|
1 |
|
3 |
|
|
2 |
|
4 |
|
|
3 |
|
5 |
|
|
0 |
空 |
6 |
|
|
1 |
|
因此,当已经匹配 ababa,即 matched = 5,下一字符失配时,可以先回退到
prefix[4] = 3。已匹配文本末尾的 aba 与模式开头的 aba 相同,新的候选无需从长度零重新开始。
前缀函数的构造¶
计算 prefix[index] 时,prefix[index - 1] 已经给出前一个模式前缀的最长边界长度,记为 matched。
若 pattern[index] == pattern[matched],就在原边界两端追加同一个字符,新边界长度增加一。
若二者不相等,当前长度 matched 无法扩展。下一候选不能随意减一,因为只有当前边界自身的相等前后缀,才
可能继续作为整个子串的相等前后缀。该候选长度正是 prefix[matched - 1]:
matched = prefix[matched - 1]
回退后仍使用同一个 pattern[index] 重新比较。若继续失配,就沿前缀函数链尝试更短边界;若最终退到零,
只需判断当前字符能否与模式首字符形成长度为一的边界。
这个构造过程与文本匹配使用同一种状态转换:都在失配时寻找“当前已匹配内容的最长可复用后缀”。区别只是构造 阶段的字符来自模式本身。
文本扫描¶
kmpSearch 令 matched 表示处理当前文本字符之前,文本已读前缀的末尾有多少个字符等于模式前缀。
处理 text[index] 时:
若它与
pattern[matched]不同,沿前缀函数缩短matched;每次回退后仍用同一个
text[index]重新比较,因为该字符尚未被任何新候选消费;若字符相等,令
matched增加一;若
matched == m,模式已经在当前位置结束。
以 text = "abababaca"、pattern = "ababaca" 为例:文本前五个字符使 matched 达到 5。
处理下标 5 的字符 b 时,它与模式下标 5 的 c 失配,于是回退到 prefix[4] = 3。
此时同一个文本字符 b 与模式下标 3 的 b 匹配,matched 变为 4;之后继续匹配
a、c、a,最终在文本下标 8 完成匹配,起点为 8 - 7 + 1 = 2。
文本下标没有退回到旧起点之后重新扫描。前缀函数已经证明,被跳过的更长候选必然失配,而保留下来的模式前缀 已经与文本已读后缀相等。
首次出现位置¶
文本按下标从左到右处理。第一次出现 matched == m 时,得到的是结束位置最小的完整匹配。所有匹配长度都为
m,结束位置越小,起始位置 index - m + 1 也越小,因此可以立即返回。
如果模式比文本长,扫描过程中 matched 不可能达到 m,最终自然返回 -1,无需单独分支。
代码演进¶
naiveSearch 为每个候选起点重新从模式首字符开始比较。一次失配会把已经匹配的全部前缀信息清空,文本字符
可能在后续起点中被重复读取。
KMP 先用 buildPrefix 为模式的每个前缀记录最长可复用边界。kmpSearch 失配时不再枚举下一个文本起点,
而是沿边界链直接跳过已经证明不可能的候选;文本下标始终向右,只调整模式已匹配长度。
公开入口采用 kmpSearch。它把逐起点的重复比较替换为一次模式预处理和一次文本扫描,在重复结构明显的输入上
仍保持线性时间。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
主要代价 |
|---|---|---|---|
逐起点验证 |
|
|
相邻起点可能重复比较相同文本字符 |
KMP |
|
|
构造前缀函数并单向扫描文本 |
构造前缀函数时,index 只向右移动,matched 的每次回退都会严格减小;其总比较次数为 O(m)。
文本扫描同理,文本下标只前进,matched 的增长与回退总量为线性级别,因此扫描为 O(n)。前缀数组保存
m 个整数,工作空间为 O(m)。