一天一道算法题day07

找出字符中第一个匹配的下标

题目描述

给你两个字符串 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 通过部分匹配表有效减少了字符的重复比较，显著提升了效率。