Implement strStr

https://leetcode.com/problems/implement-strstr

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:

1. 0 <= haystack.length, needle.length <= 5 * 104
2. haystack and needle consist of only lower-case English characters.

Implementation 1 : Naive

classSolution {
publicintstrStr(Stringhaystack, Stringneedle) {
intn = haystack.length();
intm = needle.length();
if(m > n)
return -1;
for(inti = 0; i < n -m +1; i++) {
if(haystack.substring(i,(i+m)).equals(needle))
returni;
}
return -1;
}
}

Implementation 2 : KMP Algorithm

classSolution {
publicintstrStr(Stringt, Stringp) {
intn = t.length();
intm = p.length();
if (m == 0) return0;
int[] pi = computePrefix(p);
intk = -1;
for (inti = 0; i < n; i++) {
while (k >= 0 && p.charAt(k + 1) != t.charAt(i)) {
k = pi[k];
}
if (p.charAt(k + 1) == t.charAt(i)) {
k++;
}
if (k == m - 1) {
returni - m + 1;
}
}
return -1;
}
privateint[] computePrefix(Stringp) {
intm = p.length();
int[] pi = newint[m];
pi[0] = -1;
intk = -1;
for (inti = 1; i < m; i++) {
while (k >= 0 && p.charAt(k + 1) != p.charAt(i)) {
k = pi[k];
}
if (p.charAt(k + 1) == p.charAt(i)) {
k++;
}
pi[i] = k;
}
returnpi;
}
}

Implementation 3 : Rabin Karp Algorithm

classSolution {
publicintstrStr(Stringt, Stringp) {
intn = t.length();
intm = p.length();
if (m == 0) return0;
intpCode = hashCode(p);
for(inti = 0; i < n-m+1; i++) {
Stringsubstr = t.substring(i,(i+m));
inttextCode = hashCode(substr);
if(pCode == textCode) {
if(isMatch(substr,p))
returni;
}
}
return -1;
}
privateinthashCode(Strings) {
if(s.length() == 0)
return0;
inthashCode = 0;
for(charch : s.toCharArray()) {
hashCode += (ch - 'a') + 1;
}
returnhashCode;
}
privatebooleanisMatch(Strings , Stringpattern) {
intm = pattern.length();
for(inti = 0; i < m; i++) {
if(s.charAt(i) != pattern.charAt(i))
returnfalse;
}
returntrue;
}
}

Implementation 4 : Rabin Karp (Rolling Hash)

classSolution {
publicintstrStr(Stringhaystack, Stringneedle) {
intn = haystack.length();
intm = needle.length();
if(m > n)
return -1;
intneedleHash = 0;
inthaystackHash = 0;
// lets calculate the starting hashfor(inti = 0; i < m; i++) {
needleHash += ((needle.charAt(i) - 'a' + 1));
haystackHash += ((haystack.charAt(i) - 'a' + 1));
}
for(inti=0; i < n - m +1; i++) {
Stringsubstr = haystack.substring(i,(i+m));
if(needleHash == haystackHash && substr.equals(needle)) {
returni;
}
// rolling hashif(i != n -m) {
haystackHash = haystackHash - (haystack.charAt(i) - 'a' + 1);
haystackHash += haystack.charAt(i+m) - 'a' + 1;
}
}
return -1;
}
}

Implementation 5 : Rabin Karp (Rolling Hash, Overflow issue)

classSolution {
publicintstrStr(Stringhaystack, Stringneedle) {
intn = haystack.length();
intm = needle.length();
if(m > n)
return -1;
intbase = 26;
intneedleHash = 0;
inthaystackHash = 0;
// lets calculate the starting hashfor(inti = 0; i < m; i++) {
intpower = (int) Math.pow(base, m-i-1);
needleHash += ((needle.charAt(i) - 'a' + 1) * power);
haystackHash += ((haystack.charAt(i) - 'a' + 1) * power);
}
for(inti=0; i < n - m +1; i++) {
Stringsubstr = haystack.substring(i,(i+m));
if(needleHash == haystackHash && substr.equals(needle)) {
returni;
}
// rolling hashif(i != n -m) {
haystackHash = haystackHash - (haystack.charAt(i) - 'a' + 1) * (int)Math.pow(base,m-1);
haystackHash = haystackHash * base;
haystackHash += haystack.charAt(i+m) - 'a' + 1;
}
}
return -1;
}
}

References :

1. https://www.youtube.com/watch?v=V5-7GzOfADQ (Abdul Bari)
2. https://www.youtube.com/watch?v=PcYtBG29Dz4 (Happygirlzt, Java Implementation)