```
public int strStr(String haystack, String needle) {
//KMP algorithms
if(needle.equals("")) return 0;
if(haystack.equals("")) return -1;
char[] arr = needle.toCharArray();
int[] next = makeNext(arr);
int i = 0, j = 0;
while (i < haystack.length()) {
while (j >= 0 && haystack.charAt(i) != arr[j]) j = next[j];
i++;
j++;
if (j == needle.length()) return i - j;
}
return -1;
}
private int[] makeNext(char[] arr){
int len = arr.length;
int[] next = new int[len + 1];
next[0] = -1;
int i = 0, j = -1;
while (i < len) {
while (j >= 0 && arr[i] != arr[j]) j = next[j];
i++;
j++;
next[i] = j;
}
return next;
}
```