代码随想录训练营｜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）
使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配
记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。

下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。
因为要找前面字符串的最长相同的前缀和后缀。所以要看前一位的 前缀表的数值。

/**
 * 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://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

文章讲解： https://programmercarl.com/0028.实现strStr.html

视频讲解：https://www.bilibili.com/video/BV1PD4y1o7nd/
             https://www.bilibili.com/video/BV1M5411j7Xx/