> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/string/hard/28.-find-the-index-of-the-first-occurrence-in-a-string-kmp-algorithm.md).

# 28. Find the Index of the First Occurrence in a String / KMP Algorithm

KMP

## Problem Statement

<br>

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`.

&#x20;

**Example 1:**

<pre><code><strong>Input: haystack = "sadbutsad", needle = "sad"
</strong><strong>Output: 0
</strong><strong>Explanation: "sad" occurs at index 0 and 6.
</strong>The first occurrence is at index 0, so we return 0.
</code></pre>

**Example 2:**

<pre><code><strong>Input: haystack = "leetcode", needle = "leeto"
</strong><strong>Output: -1
</strong><strong>Explanation: "leeto" did not occur in "leetcode", so we return -1.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= haystack.length, needle.length <= 104`
* `haystack` and `needle` consist of only lowercase English characters.

## Intuition

```
Approach 1: 
Brute Force In n*m we match the string 

Approach 2: KMP Algorithm O(m+n)

We try to eliminate the repeated comparision by trick
n = AAAXAAAA
m = AAAA

First maintain a Longest Prefix Suffix array, Which maintains the longest prefix suff
At the point

LPS = 0 1 2 3
  -- 
A A A A
-- 

Then Using this eliminate the repeated comparision
Refer more for video
```

### Links

<https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/>

### Video Links

<https://www.youtube.com/watch?v=JoF0Z7nVSrA&ab_channel=NeetCode>

### Approach 1:

```
Brute Force
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
        int i=0;

        while(i<n){
            int k=i, j=0;

            while(k<n and j<n){
                if(haystack[k] == needle[j]){
                    k++; j++;
                }

                else
                    break;
            }

            if(j == m)
                return k-m;

            i++;
        }

        return -1;
    }
};
```

{% endcode %}

### Approach 2:

```
KMP
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
        vector<int> lps(m,0);

        int prev=0;
        int i=1;

        while(i<m){
            if(needle[i] == needle[prev]){
                lps[i] = prev + 1;
                prev++; i++;
            }
            else if(prev == 0){
                lps[i] = 0;
                i++;
            }
            else
                prev = lps[prev-1];
        }

        i=0;
        int j=0;

        while(i<n){
            if(haystack[i] == needle[j]){
                i++; j++;
            }
            else{
                if(j==0)
                    i++;
                else
                    j = lps[j-1];
            }

            if(j == m)
                return i-m;
        }

        return -1;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###