> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0028-implement-strstr.md).

# 0028. Implement strStr(solutions/)

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

## Description

Implement [strStr()](http://www.cplusplus.com/reference/cstring/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()](http://www.cplusplus.com/reference/cstring/strstr/) and Java's [indexOf()](https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf\(java.lang.String\)).

**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/>

```java
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
*/
```