0028. Find the Index of the First Occurrence in a String ======================================================== 题目信息 -------- :题号: 0028. 找出字符串中第一个匹配项的下标 :难度: Easy :主题: 字符串、模式匹配、前缀函数、KMP :原题: `LeetCode 0028 `_ :重点: 从逐起点重新匹配,推导到复用已匹配后缀,并用前缀函数在失配时跳过不可能起点 题目重述 -------- 给定字符串 ``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++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: int naiveSearch(const std::string& text, const std::string& pattern) { const int n = static_cast(text.size()); const int m = static_cast(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 buildPrefix(const std::string& pattern) { const int m = static_cast(pattern.size()); std::vector 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 prefix = buildPrefix(pattern); int matched = 0; for (int index = 0; index < static_cast(text.size()); ++index) { while (matched > 0 && text[index] != pattern[matched]) { matched = prefix[matched - 1]; } if (text[index] == pattern[matched]) { ++matched; } if (matched == static_cast(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`` 个字符: .. code-block:: text 文本已读后缀: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`` 的前缀函数为: .. list-table:: :header-rows: 1 * - ``index`` - 字符 - 当前子串 - ``prefix[index]`` - 最长边界 * - 0 - ``a`` - ``a`` - 0 - 空 * - 1 - ``b`` - ``ab`` - 0 - 空 * - 2 - ``a`` - ``aba`` - 1 - ``a`` * - 3 - ``b`` - ``abab`` - 2 - ``ab`` * - 4 - ``a`` - ``ababa`` - 3 - ``aba`` * - 5 - ``c`` - ``ababac`` - 0 - 空 * - 6 - ``a`` - ``ababaca`` - 1 - ``a`` 因此,当已经匹配 ``ababa``,即 ``matched = 5``,下一字符失配时,可以先回退到 ``prefix[4] = 3``。已匹配文本末尾的 ``aba`` 与模式开头的 ``aba`` 相同,新的候选无需从长度零重新开始。 前缀函数的构造 ~~~~~~~~~~~~~~ 计算 ``prefix[index]`` 时,``prefix[index - 1]`` 已经给出前一个模式前缀的最长边界长度,记为 ``matched``。 若 ``pattern[index] == pattern[matched]``,就在原边界两端追加同一个字符,新边界长度增加一。 若二者不相等,当前长度 ``matched`` 无法扩展。下一候选不能随意减一,因为只有当前边界自身的相等前后缀,才 可能继续作为整个子串的相等前后缀。该候选长度正是 ``prefix[matched - 1]``: .. code-block:: text 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``。它把逐起点的重复比较替换为一次模式预处理和一次文本扫描,在重复结构明显的输入上 仍保持线性时间。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要代价 * - 逐起点验证 - ``O(nm)`` - ``O(1)`` - 相邻起点可能重复比较相同文本字符 * - KMP - ``O(n+m)`` - ``O(m)`` - 构造前缀函数并单向扫描文本 构造前缀函数时,``index`` 只向右移动,``matched`` 的每次回退都会严格减小;其总比较次数为 ``O(m)``。 文本扫描同理,文本下标只前进,``matched`` 的增长与回退总量为线性级别,因此扫描为 ``O(n)``。前缀数组保存 ``m`` 个整数,工作空间为 ``O(m)``。