登录社区云，与社区用户共同成长
邀请您加入社区
LeetCode 28. Implement strStr() (Easy) 主要知识点：字符串、KMP算法；优先级：2
本文介绍了LeetCode 28题"找出字符串中第一个匹配项的下标"的两种解法：暴力匹配和KMP算法。暴力匹配通过逐个字符比较实现，时间复杂度O(m×n)；KMP算法利用next数组跳过不必要匹配，时间复杂度O(m+n)。文章详细解释了KMP的核心思想，包括next数组的定义和构建过程，并提供了Python和Java的代码实现。两种方法各具特点：暴力匹配简单直观，KMP更高效但实现复杂，适合处理长
本文介绍了两种判断字符串是否由重复子串构成的算法。暴力解法通过枚举所有可能的子串长度（最多到字符串长度一半），检查是否能通过重复拼接构成原字符串，时间复杂度O(n²)，空间复杂度O(1)。更优的KMP算法通过将原字符串拼接后掐头去尾，在其中查找原字符串来判断是否存在重复子串，时间复杂度O(n)，空间复杂度O(n)。KMP算法虽然效率更高，但实现较为复杂，涉及构建next数组和模式匹配过程。
本文分析了LeetCode字符串匹配问题的暴力解法及优化方案。题目要求在haystack中找出needle首次出现的下标，不存在则返回-1。给出的初始代码存在数组越界风险（未限制内层循环范围）和冗余变量问题。修正版规范代码通过设置外层循环上限为n-m避免越界，使用bool变量提升可读性，时间复杂度O(n*m)。文章还对比了KMP算法（O(n+m)）和库函数实现，指出暴力解法适合入门但需注意：1）主
用 KMP 分别找出三者在 `s` 中的所有匹配位置，然后用双指针枚举 `mid` 的每个出现位置，寻找最靠右的合法 `left` 和最靠左的合法 `right`，使得子串长度最短。3. 空串处理：`kmpAll` 对空 pattern 返回 `[0..n]`，完美覆盖 `p = "**"`、`"a**"`、`"**a"` 等边界情况，无需额外特判。`s="madlogic", p="*adlog
该题的核心思路是将模式串 `p` 按两个 `'*'` 分割为三个子串 `a, b, c`，用 KMP 算法找到每个子串在 `s` 中的所有出现位置，然后枚举中间子串 `b` 的每个出现位置，通过二分查找找到最优的 `a` 和 `c` 的位置，从而得到最短匹配子串长度。2. KMP 匹配：对 `a`、`b`、`c` 分别在 `s` 中做 KMP 匹配，记录所有出现位置。1. 分割模式串：将 `p`
next[i]（或称pi[i]）表示模式串p[0...i-1]的最长公共真前后缀的长度。换句话说，它是p的前i个字符组成的子串中，既是前缀又是后缀的最长长度（且长度小于i例如（约定）（"a" 没有真前后缀）（"ab" 没有）（"aba" 的前缀 "a" = 后缀 "a"）（"abab" 的前缀 "ab" = 后缀 "ab"）（"ababa" 的前缀 "aba" = 后缀 "aba"）在 KMP 中
利用KMP中的next数组和空格巧妙解决重复子字符串的对比问题
2. KMP 匹配：问题转化为在 `diff` 数组中统计 `pattern` 出现的次数。j = lps[j-1]// 继续匹配下一个（允许重叠）`diff` 数组占用 O(n)，LPS 数组占用 O(m)。// 2. 使用 KMP 算法统计 pattern 在 diff 中的出现次数。预处理 O(n)，KMP 匹配 O(n + m)。// KMP 算法，返回 pattern 在 text 中的
2. KMP 匹配：问题转化为在 `diff` 数组中，有多少个子数组等于 `pattern`。由于 `n` 最大为 10^6，必须使用 KMP 算法在 O(n+m) 时间内完成。// pattern[0] 都不匹配，text 指针前进。// 计算两个数的符号关系：1 表示 a < b，-1 表示 a > b，0 表示相等。// KMP 算法，返回 pattern 在 text 中的出现次数。//
4道LeetCode题目645题1365题448题 KMP算法Sunday算法
得到 posA 和 posB 两个有序数组后，对于每个 posA[i]，我们移动指针 j 指向 posB 中第一个满足 posB[j] + k >= posA[i] 的位置。此时若 |posA[i] - posB[j]| <= k，则 posA[i] 为美丽下标。相比暴力匹配，KMP 利用前缀函数（next 数组）避免重复比较，时间复杂度 O(|s| + |a|) 和 O(|s| + |b|)。·
