找出字符串中第一个匹配项的下标
难度:
标签:
题目描述
给你两个字符串 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 。
提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
代码结果
运行时间: 56 ms, 内存: 15.9 MB
/*
* 思路：
* 虽然Stream API不太适合处理字符串查找问题，
* 但可以利用Stream API将字符串转化为字符流，然后查找匹配的子字符串。
* 这是一种不常见但可行的做法。
*/
import java.util.stream.IntStream;
public class Solution {
public int strStr(String haystack, String needle) {
int needleLength = needle.length();
return IntStream.range(0, haystack.length() - needleLength + 1)
.filter(i -> haystack.substring(i, i + needleLength).equals(needle))
.findFirst()
.orElse(-1);
}
}解释
方法:
这个题解使用了 KMP 算法来解决字符串匹配问题。首先通过 gen_nxt() 函数生成 needle 字符串的 next 数组，next[i] 表示 needle[0:i] 这个子串的最长相等前后缀的长度。然后在 search() 函数中，使用 next 数组来优化匹配过程，当出现字符不匹配时，通过 next 数组将 needle 向右移动尽可能远的距离，避免了暴力解法中的重复匹配，从而提高了匹配效率。
时间复杂度:
O(m+n)
空间复杂度:
O(m)
代码细节讲解
🦆
在 gen_nxt() 函数中，next 数组是如何确保可以有效减少重复匹配？
▷🦆
你如何解释KMP算法在search()函数中通过next数组实现字符串的快速匹配，具体是如何操作的？
▷🦆
当 needle 字符串的第一个字符就不匹配时，算法是如何处理的？
▷🦆
如果 haystack 的长度小于 needle 的长度，KMP 算法是否有做出相应的判断避免不必要的计算？
▷