90 lines
3.3 KiB
C++
90 lines
3.3 KiB
C++
#include "s0028_find_the_index_of_the_first_occurrence_in_a_string.hpp"
|
||
|
||
// 构造字符串 s 的前缀表
|
||
// 在 getNext() 函数中，我们假设 s.length() >= 2
|
||
void S0028::getNext(int* next, const string& s) {
|
||
// j 有两重含义：
|
||
// 1. 前缀的末尾下标
|
||
// 2. 最长相同前后缀的长度
|
||
// i 的含义是后缀的末尾下标
|
||
// 初始化 j 为 0
|
||
int j{0};
|
||
// next[0] 很显然一定是为 0 的
|
||
next[0] = 0;
|
||
// 开始迭代
|
||
// 我们的目标是在每次迭代的过程中，找到最长相同前后缀
|
||
// s[0...j] == s[?...i]
|
||
// i 从 1 开始迭代，因为 length >= 2 ，我们没必要讨论
|
||
// i == 0 的情况
|
||
int len = s.size();
|
||
for (int i{1}; i < len; ++i) {
|
||
// 当 s[j] 和 s[i] 不想等时，即前后缀不匹配的时候
|
||
// 前缀末尾的下标 j 需要进行回退
|
||
// a a a f a a a f
|
||
// j i
|
||
// 回退到什么位置呢？
|
||
// 注意观察，s[j] 和 s[i] 虽然不想等，但是前面这一段
|
||
// aaafaaa 有着公共前后缀 aaa ，所以我们可以试着跳到
|
||
// 前缀 aaa 的后面那个元素的位置 f，然后比较前缀 aaaf
|
||
// 和后缀 aaaf 是否相同。
|
||
// a a a f a a a f
|
||
// j i
|
||
// j i
|
||
// 由于前缀和后缀都有着公共的 aaa ，所以我们只需要比较
|
||
// s[j] 和 s[i] 是否相同就行了。
|
||
// 如果不相同，继续回退，直到 j 回退到起始位置 0。
|
||
// 怎么把 j 跳到 f 的位置呢？f 在 aaa 的后面，aaa 是
|
||
// aaafaaa 的最长公共前缀，所以 f 的下标就是 next[j - 1]
|
||
while (j > 0 && s[i] != s[j]) {
|
||
j = next[j - 1];
|
||
}
|
||
// 接下来处理当 s[j] == s[i] 的情况
|
||
// 这种情况很简单，就是公共前后缀的长度增加了 1
|
||
// 而由于 for 语句中的 ++i 使得后缀末尾 i 已经自增了 1
|
||
// 我们只需要再让前缀末尾 j 自增 1 即可
|
||
if (s[i] == s[j]) {
|
||
++j;
|
||
}
|
||
// 两种情况都处理完了，接下来更新 next[i]
|
||
// 由于我们之前让 j 自增了 1，所以其实现在的情况是
|
||
// 前缀 [0, j - 1] 和 后缀 [?, i] 相同
|
||
// 然而 next[i] 是指最长公共前后缀的长度，因此长度可以用
|
||
// j 来描述。
|
||
next[i] = j;
|
||
}
|
||
}
|
||
|
||
int S0028::strStr(string haystack, string needle) {
|
||
int haystackLen = haystack.size();
|
||
int needleLen = needle.size();
|
||
if (needleLen == 0) {
|
||
return 0;
|
||
}
|
||
// 开始创建 needle 的前缀表
|
||
int next[needleLen];
|
||
getNext(next, needle);
|
||
// j 用来索引 needle ，它有两层含义
|
||
// 1. 前缀的末尾下标
|
||
// 2. 最长相同前后缀的长度
|
||
int j = 0;
|
||
// 开始迭代
|
||
// 接下来的操作和 getNext() 中的迭代非常相似
|
||
// 不过注意，现在 i 从 0 开始迭代，之所以不像 getNext()
|
||
// 中那样从 1 开始迭代是因为 getNext() 不需要考虑 i == 0
|
||
for (int i{0}; i < haystackLen; ++i) {
|
||
// 首先讨论末尾不匹配的情况，我们需要回退 j
|
||
while (j > 0 && needle[j] != haystack[i]) {
|
||
j = next[j - 1];
|
||
}
|
||
// 接下来处理末尾相同的情况，那好说，直接往前推
|
||
if (needle[j] == haystack[i]) {
|
||
++j;
|
||
}
|
||
// 成功找到匹配字符串，返回
|
||
if (j == needleLen) {
|
||
return i - needleLen + 1;
|
||
}
|
||
}
|
||
return -1;
|
||
}
|