I solved this problem using both bruteforce and kmp, whereas the bruteforce took 15ms, kmp 18ms. Is there something wrong with my kmp solution? what is the run time of your kmp code? I would be much appreciated if some one could tell me his/her run time for reference
below is my kmp code:
public class Solution {
public int strStr(String haystack, String needle) {
int len = needle.length();
if (haystack == null  needle == null  (haystack.length() == 0&&len != 0)) return 1;
if (len == 0) return 0;
int[] lsp = new int[len];
lsp[0] = 0;
for (int i=1;i<len;i++) {
lsp[i] = 0;
int j = lsp[i1];
while (j>0 && needle.charAt(i) != needle.charAt(j))
j = lsp[j1];
if (needle.charAt(i) == needle.charAt(j)) lsp[i] = j + 1;
}
for (int i=0, j=0;i<haystack.length();i++) {
while (j>0 && haystack.charAt(i) != needle.charAt(j)) j = lsp[j1];
if (haystack.charAt(i) == needle.charAt(j)) j++;
if (j == len) return (ilen+1);
}
return 1;

}