# 0028. Implement strStr()

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Implement strStr()](https://leetcode.com/problems/implement-strstr/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0028-implement-strStr)

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\)).
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `0 <= haystack.length, needle.length <= 5 * 10^4`
* `haystack` and `needle` consist of only lower-case English characters.

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

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
It's quite straightforward to iterate through the input string (haystack) and check whether the target string (needle) is part of it or not.

Instead, **let's use the&#x20;*****KMP algorithm*****&#x20;to solve this problem.**
{% endhint %}

For using KMP, we first create the **LPS (Longest proper Prefix also Suffix) table.** Then **we use the same algorithm that creates the LPS table but with few tweaks with the LPS table as a reference** to find the answer.

* To create an LPS table, we **use two pointers to iterate the target string (needle).** \
  One for **iterating** `moveP = 0`\
  Second for **pointing to the previous same char by jumping** `jumpP = 1`
  * **If two chars are the same** (pointed by moveP and jumpP respectively)\
    Mark the table by `table[moveP] = jumpP + 1` and move both pointers by increasing their index.
  * **If two chars are not the same**
    * If `jumpP == 0` , it means that we cannot jump further.\
      Set `table[moveP] = 0` and `moveP += 1`
    * Otherwise, we jump by `jump = LPSTable[jumpP - 1]`
* After we have the LPS table, **we use the same algorithm with few tweaks**
  * `moveP, jumpP = 0, 0`
  * Compare between two strings by `haystack[moveP], needle[jumpP]`
  * For jumping `jumpP = LPSTable[jumpP - 1]`
  * **Return condition** If `jumpP == len(needle)`, return `moveP - len(needle)`
    {% endtab %}
    {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # (base case)
        if not needle: return 0
        if not haystack: return -1
        if len(needle) > len(haystack): return -1
        
        # ==================================================
        #  String + Two Pointer                            =
        # ==================================================
        # n = length of haystack
        # m = length of needls
        # time  : O(n*m)
        # space : O(1)
        
        start, end = 0, len(needle)
        
        while end-1 < len(haystack):
            if haystack[start:end] == needle: return start
            else:
                start += 1
                end   += 1
            
        return -1
        
        '''
        # ==================================================
        #  Python built-in Function                        =
        # ==================================================
        try:
            return haystack.index( needle )
        except:
            return -1
        '''
```

{% endtab %}

{% tab title="🤖 Python3 (KMP)" %}

```python
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # (base case)
        if not needle: return 0
        if not haystack: return -1
        if len(needle) > len(haystack): return -1

        # ==================================================
        #  KMP Pattern Matching (Substring search)         =
        # ==================================================
        # n = length of haystack
        # m = length of needls
        # time  : O(n+m)
        # space : O(m)

        # (1) build LPS table (Longest proper Prefix also Suffix)
        # time  : O(n)
        # space : O(n)
        def LPS(string: str, length: int) -> list:
            '''
            Two pointers, jump and move, point to GOLDEN string
            '''
            jumpP, moveP = 0, 1
            table = [0] + [-1]*( length - 1 )

            while moveP < length:
                if string[jumpP] != string[moveP]:
                    if jumpP == 0:
                        table[moveP] = 0
                        moveP += 1
                    else:
                        jumpP = table[jumpP-1]

                else:
                    table[moveP] = jumpP + 1

                    jumpP += 1
                    moveP += 1

            return table

        # (2) use LPS table to do pattern matching
        # time  : O(m)
        # space : O(1)
        def KMP(str1: str, str2: str, LPSTable: list) -> int:
            '''
            Two pointers:
            - move pointer point to TARGET string (haystack)
            - jump pointer point to LPS table / GOLDEN string (needle)
            '''
            jumpP, moveP = 0, 0

            while moveP < len(str1):
                if str1[moveP] != str2[jumpP]:
                    if jumpP == 0:
                        moveP += 1
                    else:
                        jumpP = LPSTable[jumpP-1]

                else:
                    jumpP += 1
                    moveP += 1

                # Meet the end, return starting index
                if jumpP == len(str2): return moveP - len(str2)

            return -1

        LPSTable = LPS(needle, len(needle))
        return KMP(haystack, needle, LPSTable)
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n*m)
     * @space : O(1)
     */

    public int strStr(String haystack, String needle) {
        /* base case */
        if(needle.length() == 0) return 0;
        if(haystack.length() == 0 || needle.length() > haystack.length()) return -1;
        
        for(int i=0; i<(haystack.length()-needle.length()+1);i++) {
            if (haystack.substring(i,i+needle.length()).equals(needle)) return i;
        }
        return -1;
    }
}
```

{% endtab %}
{% endtabs %}