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
40
41
42
43
44
45
46
47
48
49
50
51
| package com.zq.JVM;
public class test2 {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.strStr("aabaabaaf", "aabaaf"));
}
}
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0) {
return 0;
}
int[] next = new int[needle.length()];
getNext(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 - j + 1;
}
}
return -1;
}
private void getNext(int[] next, String s) {
int j = 0;
next[0] = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i)) {
j = next[j - 1];
}
if (s.charAt(j) == s.charAt(i)) {
j++;
}
next[i] = j;
}
}
}
|
- 原字符串str, 将被匹配的模式串pattern, str.length()>=pattern.length();
- next数组长度与pattern.length()相等
- 前缀: 不包含最后一个字符的所有以第一个字符开头的连续子串
- 后缀: 不包含第一个字符的所有以最后一个字符结尾的连续子串
==为什么这样回退正确?==
pattern的冲突字符f前的最长相等前后缀为aa, 而对于str, 在冲突字符之前都是匹配的, 所以pattern中f前的aa和str中冲突字符之前aa是匹配的, 而根据最长相等前后缀, pattern中f前的aa和pattern的前缀aa是相同的 =>
pattern的前缀aa和str中冲突字符之前的aa是匹配的
参考
leetcode-master/0028.实现strStr.md at master · youngyangyang04/leetcode-master · GitHub (zhou29.top)
