leetcode28题解法
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
public class N28 {
public static int strStr(String haystack, String needle) {
if(needle.length()==0){
return 0;
}
int[] next=getNext(needle);
int i=0,j=0;
while (i<haystack.length()&&j<needle.length()){
if(j==-1||haystack.charAt(i)==needle.charAt(j)){
i++;
j++;
}else {
j=next[j];
}
}
if(j==needle.length()){
return i-j;
}
else {
return -1;
}
}
public static int[] getNext(String needle){
char[] str=needle.toCharArray();
int[] next=new int[needle.length()];
next[0]=-1;
int j=0,k=-1;
while (j<str.length-1){
if(k==-1||str[j]==str[k]){
next[++j]=++k;
}
else {
k=next[k];
}
}
return next;
}
public static void main(String[] args) {
strStr("mississippi", "issip");
String aaa="aaa";
aaa.indexOf("ll");
}
}
|
kmp字符串匹配算法是目前很好的的一个字符串匹配算法，通过查看大多数资料，发现next数组只与needle本身有关。
通过leetcode题解，可以把next数组里面的数字当成有限确定自动机，具体可以参考以下网址
kmp算法讲解
leetcode题解