# 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:
1. What should be the return value if the needle is empty?
2. 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
Method:

http://www.matrix67.com/blog/archives/115

Solution:

n = size of bigger string
m = size of smaller string

Time: O(n + m)
Space: O(m)

```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 = -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;
}
}```