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

# 28 Implement strStr()

## 28. [Implement strStr()](https://leetcode.com/problems/implement-strstr/description/)

## 1. Question

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.

**Example 1:**

```
Input: haystack = "hello", needle = "ll"

Output: 2
```

**Example 2:**

```
Input: haystack = "aaaaa", needle = "bba"

Output: -1
```

## 2. Implementation

**(1) KMP算法**

```java
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() == 0) {
            return 0;
        }

        if (haystack.length() < needle.length()) {
            return -1;
        }

        // KMP Algorithm
        int[] next = getNextArray(needle);
        int i = 0, j = 0;

        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                ++i;
                ++j;
            }
            else if (j != 0) {
                j = next[j - 1];
            }
            else {
                ++i;
            }
        }

        if (j == needle.length()) {
            return i - needle.length();
        }

        return -1;
    }

    public int[] getNextArray(String pattern) {
        int[] next = new int[pattern.length()];

        int index = 0;

        for (int i = 1; i < pattern.length(); ) {
            if (pattern.charAt(i) == pattern.charAt(index)) {
                next[i] = index + 1;
                ++index;
                ++i;
            }
            else if (index != 0) {
                index = next[index - 1];
            }
            else {
                next[index] = 0;
                ++i;
            }
        }
        return next;
    }
}
```

**(2) Two Pointers**

```java
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() == 0) {
            return 0;
        }

        int i = 0;
        while (i < haystack.length()) {
            if (haystack.length() - i < needle.length()) {
                break;
            }

            if (haystack.charAt(i) == needle.charAt(0)) {
                int j = i;
                while (j - i < needle.length() && haystack.charAt(j) == needle.charAt(j - i)) {
                    ++j;
                }

                if (j - i == needle.length()) {
                    return i;
                }
            }
            ++i;
        }
        return -1;
    }
}
```

## 3. Time & Space Complexity

**KMP算法**: 时间复杂度O(m + n), m是haystack的长度, n是needle的长度，空间复杂度O(n)

**Two Pointers**: 时间复杂度O(mn), 空间复杂度O(1)