Implement StrStr
Implement strStr().
strstr - locate a substring ( needle ) in a string ( haystack ).
Try not to use standard library string functions for this question.
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
NOTE: Good clarification questions:- What should be the return value if the needle is empty?
- What if both haystack and needle are empty?
For the purpose of this problem, assume that the return value should be -1 in both cases
public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int strStr(final String A, final String B) {
if (A.length() == 0 || B.length() == 0) {
return -1;
}
// A [i - j, i]
// B [0, j]
int[] table = buildFallBackTable(B);
int targetIndex = -1;
for (int searchIndex = 0; searchIndex < A.length(); searchIndex ++) {
while (targetIndex >= 0 && B.charAt(targetIndex + 1) != A.charAt(searchIndex)) {
targetIndex = table[targetIndex];
}
if (B.charAt(targetIndex + 1) == A.charAt(searchIndex)) {
targetIndex ++;
if (targetIndex == B.length() - 1) {
return searchIndex - targetIndex;
}
}
}
return -1;
}
private int[] buildFallBackTable(String B) {
int[] table = new int[B.length()];
table[0] = -1;
int fallBackIndex = -1;
for (int currentIndex = 1; currentIndex < B.length(); currentIndex ++) {
while (fallBackIndex >= 0 && B.charAt(fallBackIndex + 1) != B.charAt(currentIndex)) {
fallBackIndex = table[fallBackIndex];
}
if (B.charAt(fallBackIndex + 1) == B.charAt(currentIndex)) {
fallBackIndex ++;
}
table[currentIndex] = fallBackIndex;
}
return table;
}
}