找出字符串中第一个匹配的下标
力扣题号28
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
| 给你两个字符串 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 。
|
匹配两个字符串，首先想到的就是暴力循环，但是暴力循环的方式过于消耗时间，每次匹配失败都要重新循环匹配。KMP算法就非常适用于字符串的匹配问题。
KMP算法主要思想就是前缀表的使用。不了解的同学可以先去了解一下前缀表的知识。
前缀表的实现有不同的方式，这里就使用 不减一的方式实现
KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public int strStr(String haystack, String needle) {
if (haystack.length() == 0 || needle.length() == 0){
return -1;
}
int[] next = new int[needle.length()];
hasNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.length(); i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)){
j = next[j-1];
}
if (haystack.charAt(i) == needle.charAt(j)){
j++;
}
if (j == needle.length()){
return i - needle.length() + 1;
}
}
return -1;
}
public void hasNext(int []next, String needle){
int j = 0;
next[0] = j;
for (int i = 1; i < needle.length(); i++) {
while (needle.charAt(i) != needle.charAt(j) && j > 0){
j = next[j-1];
}
if (needle.charAt(i) == needle.charAt(j)){
j++;
}
next[i] = j;
}
}
}
|
