【字符串|LeetCode 28. Implement strStr()（实现子串定位）】原题网址：https://leetcode.com/problems/implement-strstr/
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
方法一：穷举。
public class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
if (haystack.length() < needle.length()) return -1;
char[] ha = haystack.toCharArray();
char[] na = needle.toCharArray();
for(int i = 0;
i < ha.length && i + na.length <= ha.length;
i++) {
boolean match = true;
for(int j = 0;
j < na.length;
j++) {
if (ha[i + j] != na[j]) {
match = false;
break;
}
}
if (match) return i;
}
return -1;
}
}方法二：KMP算法。
public class Solution {
public int strStr(String haystack, String needle) {
char[] ha = haystack.toCharArray();
char[] na = needle.toCharArray();
int[] kmp = new int[na.length];
for(int offset=Math.min(na.length-1, ha.length-na.length);
offset>0;
offset--) {
for(int i=0;
i+offset另一种实现：
public class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
if (haystack.length() < needle.length()) return -1;
char[] ha = haystack.toCharArray();
char[] na = needle.toCharArray();
int[] kmp = new int[na.length];
for(int i = Math.min(ha.length - na.length, na.length - 2);
i >= 1;
i--) {
for(int j = i;
j < na.length - 1;
j++) {
if (na[j - i] == na[j]) {
kmp[j + 1] = i;
} else {
break;
}
}
}int h = 0, n = 0;
while (h + na.length <= ha.length) {
if (ha[h + n] == na[n]) {
n++;
if (n == na.length) return h;
} else if (kmp[n] == 0) {
h += Math.max(n, 1);
n = 0;
} else {
h += kmp[n];
n -= kmp[n];
}
}
return -1;
}
}有一篇很牛的KMP算法介绍，参考：http://blog.csdn.net/v_july_v/article/details/7041827
看了上文之后，重新写了一下，把kmp数组看成是最大公共前后缀的长度，这样理解非常方便！
public class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
if (haystack.length() < needle.length()) return -1;
char[] ha = haystack.toCharArray();
char[] na = needle.toCharArray();
int[] len = new int[na.length];
for(int i = 1;
i < na.length && i <= ha.length - na.length;
i++) {
int j = len[i - 1];
while (j > 0 && na[j] != na[i]) j = len[j - 1];
len[i] = j + (na[j]==na[i]? 1 : 0);
}int h = 0, n = 0;
while (h + na.length <= ha.length) {
if (ha[h + n] == na[n]) {
n++;
if (n == na.length) return h;
} else if (n == 0) {
h++;
} else {
h += n - len[n - 1];
n = len[n - 1];
}
}
return -1;
}
}推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)