• 欢迎光临~

# 代码随想录训练营｜Day 9｜28

### 28. Find the Index of the First Occurrence in a String

Given two strings `needle` and `haystack`, return the index of the first occurrence of `needle` in `haystack`, or `-1` if `needle` is not part of `haystack`.

Example 1:

``````Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
``````

Example 2:

``````Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
``````

Constraints:

• `1 <= haystack.length, needle.length <= 104`
• `haystack` and `needle` consist of only lowercase English characters.

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
next数组就是一个前缀表（prefix table）

``````/**
* Using KMP Algorithm
*
* Time Complexity: O(M + N). O(N) to create lookup table. O(M) to find the
* needle in haystack.
*
* Space Complexity: O(N). This is required to save the lookup table.
*
* M = Length of haystack string. N = length of needle string.
*/
class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}

int nLen = needle.length();
int hLen = haystack.length();
if (nLen == 0) {
return 0;
}
if (hLen == 0) {
return -1;
}

int[] table = kmpLookupTable(needle);
int i = 0;
int j = 0;
while (i < hLen && j < nLen) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else {
if (j > 0) {
j = table[j - 1];
} else {
i++;
}
}
}

if (j == nLen) {
return i - j;
}
return -1;
}

private int[] kmpLookupTable(String s) {
int[] table = new int[s.length()];
int i = 1;
int index = 0;
while (i < s.length()) {
if (s.charAt(i) == s.charAt(index)) {
table[i] = index + 1;
index++;
i++;
} else {
if (index > 0) {
index = table[index - 1];
} else {
table[i] = 0;
i++;
}
}
}
return table;
}
}
``````

Time Complexity：O(m + n)
Space Complexity：O(1)

For Future References

https://www.bilibili.com/video/BV1M5411j7Xx/