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

KMP

Problem Statement

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.

Example 1:

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

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

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

C++

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;
    }
};

Approach 2:

KMP

C++

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;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems