28. Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Thought
Brute force search may expect the TLE, here apply the KMP to solve.
Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search) - Tushar Roy
KMP string matching algorithm (string/pattern search in a text) - Vivekanand Khyade
Simple example to illustrate creation of the partial match table,
after the initialization by given the pattern "abcaby",
j i
0 1 2 3 4 5 index
a b c a b y char
0 0 0 0 0 0 value
when pattern.charAt(i) == pattern.charAt(j), the prefix value be the j's index plus one,
j → i
0 1 2 3 4 5
a b c a b y
0 0 0 1 0 0
when pattern.charAt(i) != pattern.charAt(j), continuous fall back the j,
and keep comparing the two chars,
← j i
0 1 2 3 4 5
a b c a b y
0 0 0 1 0 0
...
Solution
public class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
if (haystack == null || haystack.length() == 0) return -1;
// compute the array that stores the longest subarray whose prefix is also its suffix
int[] lps = lps(needle);
int j = 0; // chars matched in pattern
for (int i = 0; i < haystack.length(); i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
// fall back the pattern pointer to previous location
j = lps[j - 1];
}
if (haystack.charAt(i) == needle.charAt(j)) {
// same chars found, move both i and j to their right direction,
// i is increase by for-loop, so just increase the j
j++;
if (j == needle.length())
return i - (j - 1);
}
}
return -1;
}
private int[] lps(String pattern) {
int[] res = new int[pattern.length()];
for (int i = 1; i < pattern.length(); i++) {
int j = res[i - 1];
while (j > 0 && pattern.charAt(i) != pattern.charAt(j))
j = res[j - 1];
if (pattern.charAt(i) == pattern.charAt(j))
j++;
res[i] = j;
}
return res;
}
}