bbb WordPress站点2022年新闻摘抄简短
找出字符中第一个匹配的下标
题目描述
给你两个字符串
haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
解题思路
暴力匹配算法。其基本思想是，从 haystack 中的每个字符位置开始，与 needle 字符串逐个进行比较，如果发现不匹配就继续移动 haystack，直到找到匹配项或搜索结束。
public int strStr(String haystack, String needle) {int m = haystack.length();int n = needle.length();if (n == 0) return 0; // 空字符串特殊处理for (int i = 0; i <= m - n; i++) {int j = 0;while (j < n && haystack.charAt(i + j) == needle.charAt(j)) {j++;}if (j == n) return i; // 匹配成功}return -1; // 未找到匹配项
}
这种方法的时间复杂度是 O(m * n)，其中 m 是 haystack 的长度，n 是 needle 的长度。当 needle 很短而 haystack 很长时，这种方法的效率会变得低下。因此，为了提高效率，可以使用 KMP 算法。
KMP 算法简介
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它通过部分匹配表（又称为前缀表）来加快匹配过程，避免重复检查已经匹配过的字符。
KMP 算法原理
KMP 的核心思想是在匹配过程中，如果发现了不匹配字符，算法会利用之前已经匹配过的字符信息，移动 needle 字符串，而不是从头开始匹配。这是通过构建部分匹配表（前缀表）来实现的。
部分匹配表存储了每个位置之前的最长相同前后缀长度。例如： 对于 needle = "abcab"，其部分匹配表为 [0, 0, 0, 1, 2]。
- 第一个字符
a没有前后缀，因此为 0。 ab没有相同的前后缀，因此为 0。abc也没有相同前后缀，为 0。abca的前缀a和后缀a匹配，为 1。abcab的前缀ab和后缀ab匹配，为 2。
KMP 算法步骤
- 构建部分匹配表（前缀表）：根据
needle构造出每个位置的最长相同前后缀长度。 - 使用部分匹配表进行匹配：在主串中逐步匹配子串，当发生不匹配时，利用部分匹配表快速跳过不必要的比较。
KMP 算法实现
public class Solution {public int strStr(String haystack, String needle) {if (needle.isEmpty()) return 0;int[] lps = computeLPSArray(needle);int i = 0, j = 0; // i 是 haystack 的索引，j 是 needle 的索引while (i < haystack.length()) {if (haystack.charAt(i) == needle.charAt(j)) {i++;j++;}if (j == needle.length()) {return i - j; // 找到匹配项，返回下标} else if (i < haystack.length() && haystack.charAt(i) != needle.charAt(j)) {if (j != 0) {j = lps[j - 1]; // 使用部分匹配表跳过重复比较} else {i++;}}}return -1; // 未找到匹配项}// 构造部分匹配表private int[] computeLPSArray(String needle) {int[] lps = new int[needle.length()];int length = 0;int i = 1;while (i < needle.length()) {if (needle.charAt(i) == needle.charAt(length)) {length++;lps[i] = length;i++;} else {if (length != 0) {length = lps[length - 1];} else {lps[i] = 0;i++;}}}return lps;}
}
复杂度分析
KMP 算法的时间复杂度为 O(m + n)，其中 m 是 haystack 的长度，n 是 needle 的长度。相比于暴力匹配算法，KMP 通过部分匹配表有效减少了字符的重复比较，显著提升了效率。