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