# why kmp takes more time than brute-force?

• I solved this problem using both brute-force and kmp, whereas the brute-force 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[i-1];
while (j>0 && needle.charAt(i) != needle.charAt(j))
j = lsp[j-1];
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[j-1];
if (haystack.charAt(i) == needle.charAt(j)) j++;
if (j == len) return (i-len+1);
}

return -1;
-
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.