It's quite straightforward to iterate through the input string (haystack) and check whether the target string (needle) is part of it or not.
Instead, let's use the KMP algorithm to solve this problem.
For using KMP, we first create the LPS (Longest proper Prefix also Suffix) table. Then we use the same algorithm that creates the LPS table but with few tweaks with the LPS table as a reference to find the answer.
To create an LPS table, we use two pointers to iterate the target string (needle).
One for iterating moveP = 0
Second for pointing to the previous same char by jumping jumpP = 1
If two chars are the same (pointed by moveP and jumpP respectively)
Mark the table by table[moveP] = jumpP + 1 and move both pointers by increasing their index.
If two chars are not the same
If jumpP == 0 , it means that we cannot jump further.
Set table[moveP] = 0 and moveP += 1
Otherwise, we jump by jump = LPSTable[jumpP - 1]
After we have the LPS table, we use the same algorithm with few tweaks
moveP, jumpP = 0, 0
Compare between two strings by haystack[moveP], needle[jumpP]
For jumping jumpP = LPSTable[jumpP - 1]
Return condition If jumpP == len(needle), return moveP - len(needle)
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# (base case)
if not needle: return 0
if not haystack: return -1
if len(needle) > len(haystack): return -1
# ==================================================
# String + Two Pointer =
# ==================================================
# n = length of haystack
# m = length of needls
# time : O(n*m)
# space : O(1)
start, end = 0, len(needle)
while end-1 < len(haystack):
if haystack[start:end] == needle: return start
else:
start += 1
end += 1
return -1
'''
# ==================================================
# Python built-in Function =
# ==================================================
try:
return haystack.index( needle )
except:
return -1
'''
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# (base case)
if not needle: return 0
if not haystack: return -1
if len(needle) > len(haystack): return -1
# ==================================================
# KMP Pattern Matching (Substring search) =
# ==================================================
# n = length of haystack
# m = length of needls
# time : O(n+m)
# space : O(m)
# (1) build LPS table (Longest proper Prefix also Suffix)
# time : O(n)
# space : O(n)
def LPS(string: str, length: int) -> list:
'''
Two pointers, jump and move, point to GOLDEN string
'''
jumpP, moveP = 0, 1
table = [0] + [-1]*( length - 1 )
while moveP < length:
if string[jumpP] != string[moveP]:
if jumpP == 0:
table[moveP] = 0
moveP += 1
else:
jumpP = table[jumpP-1]
else:
table[moveP] = jumpP + 1
jumpP += 1
moveP += 1
return table
# (2) use LPS table to do pattern matching
# time : O(m)
# space : O(1)
def KMP(str1: str, str2: str, LPSTable: list) -> int:
'''
Two pointers:
- move pointer point to TARGET string (haystack)
- jump pointer point to LPS table / GOLDEN string (needle)
'''
jumpP, moveP = 0, 0
while moveP < len(str1):
if str1[moveP] != str2[jumpP]:
if jumpP == 0:
moveP += 1
else:
jumpP = LPSTable[jumpP-1]
else:
jumpP += 1
moveP += 1
# Meet the end, return starting index
if jumpP == len(str2): return moveP - len(str2)
return -1
LPSTable = LPS(needle, len(needle))
return KMP(haystack, needle, LPSTable)
class Solution {
/**
* @time : O(n*m)
* @space : O(1)
*/
public int strStr(String haystack, String needle) {
/* base case */
if(needle.length() == 0) return 0;
if(haystack.length() == 0 || needle.length() > haystack.length()) return -1;
for(int i=0; i<(haystack.length()-needle.length()+1);i++) {
if (haystack.substring(i,i+needle.length()).equals(needle)) return i;
}
return -1;
}
}