Implement 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() and Java's indexOf().

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

`0 <= haystack.length, needle.length <= 5 * 10`

^{4}`haystack`

and`needle`

consist of only lower-case English characters.

class Solution {
public int strStr(String haystack, String needle) {
if(haystack==null || needle== null || needle.length()>haystack.length()){
return -1;
}
int[] parr = KmpPreprocess(needle);
int i=0;
int j=0;
while(i<haystack.length() && j<needle.length()){
if(haystack.charAt(i) == needle.charAt(j)){
i++;
j++;
}
else if(j>0){
j=parr[j-1];
}
else{
i++;
}
}
if(j==needle.length()){
return i-j;
}
return -1;
}
private int[] KmpPreprocess(String pattern){
int[] parr = new int[pattern.length()];
int i=0;
int j=1;
while(j<pattern.length()){
if(pattern.charAt(i)==pattern.charAt(j)){
parr[j]=i+1;
i++;
j++;
}
else if(i>0){
i = parr[i-1];
}
else{
j++;
}
}
return parr;
}
}

We can solve this question using both the Naive Approaches as well as using KMP Algorithm.

Naive Approach: Traverse all the possible starting points of `haystack`

(from `0`

to `haystack.length() - needle.length()`

) and see if the following characters in `haystack`

match those of `needle`

.

Time Complexity: O(mn)

Space Complexity: O(1)

KMP Algorithm: Finally comes the KMP algorithm. You may refer to KMP on jBoxer's blog for some explanations.

Time Complexity: O(m+n)

Space Complexity: O(n)