0028. Implement strStr(solutions/)

https://leetcode.com/problems/implement-strstr

Description

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example 1:

**Input:** haystack = "hello", needle = "ll"
**Output:** 2

Example 2:

**Input:** haystack = "aaaaa", needle = "bba"
**Output:** -1

Example 3:

**Input:** haystack = "", needle = ""
**Output:** 0

Constraints:

• 0 <= haystack.length, needle.length <= 5 * 104

• haystack and needle consist of only lower-case English characters.

ac1: brute force

https://leetcode.com/problems/implement-strstr/

public int strStr(String s, String t) {
        if (t.isEmpty()) return 0; // edge case: "",""=>0  "a",""=>0
        for (int i = 0; i <= s.length() - t.length(); i++) {
            for (int j = 0; j < t.length() && s.charAt(i + j) == t.charAt(j); j++)
                if (j == t.length() - 1) return i;
        }
        return -1;
    }

ac2: KMP algorithm

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.equals("")) return 0;
        if (haystack.length() < needle.length()) return -1;

        int[] kmp = getPatternTable(needle);
        int h = 0, n = 0;
        while (h < haystack.length() && n < needle.length()) {
            if (haystack.charAt(h) == needle.charAt(n)) {
                h++;
                n++;
            } else {
                if (n == 0) h++;
                else n = kmp[n-1];
            }
        }
        // if (n == needle.length()) return h - needle.length(); // find needle
        // if (h == haystack.length()) return -1; // haystack finish, needle still has remaining.

        return n == needle.length() ? h - needle.length() : -1;
    }

    private int[] getPatternTable(String s) {
        int n = s.length();
        int [] kmp = new int[n];
        int l = 0, r = 1;
        while (r < n) {
            if (s.charAt(l) == s.charAt(r)) {
                kmp[r] = l + 1;
                l++;
                r++;
            } else {
                if (l == 0) {
                    r++;
                } else {
                    l = kmp[l-1];
                }
            }
        }

        return kmp;
    }
}


/*
KMP, 1) build pattern table; 2) match two String
ABCABDKJABCABCABD
*/