# Why my solution based on KMP exceeds time limit?

• Time limit exceeded
Last executed input:
"aaaaaaaaaaaaaaaaa.......
......aaaaaaaaaaaab"

I don't know where my code should be improved.

``````public int strStr(String haystack, String needle) {

int result = -1, i = 0, j = 0;

if (haystack==null || needle==null || needle.length()>haystack.length())
return result;

if (needle.length()==0) return 0;

while (i<haystack.length() && j<needle.length()) {
if (haystack.charAt(i)==needle.charAt(j)) {
i++; //i is the index of character in the haystack
j++; //j is the max match length of the needle with the haystack
if (j==needle.length()) {
//Find the first occurrence of the needle as it may match the haystack several times
result = (result>0)?Math.min(result, i-j+1):(i-j+1);
}
}
else {
if (j!=0) {
/*If the needle matches the haystack till the jth character, but does not at the (j+1)th one
*We need to calculate i where the next match work starts
*So we calculate "step" besed on KMP "partial match table"
*/
i -= step(needle, j); //New match starts from the ith character of the haystack
j = 0; //Reset j, so that new match starts from the first character of the needle
}
else {
i++;
}
}
}

return result;

}

//Below is the function of finding "step" base on KMP "partial match table".
public int step(String needle, int length) {

int result = 0;
String s1 = "", s2 = "";

for (int k=0; k<length; k++) {
s1 = s1 + needle.charAt(k); //s1 combines characters from the left of the needle to the right
s2 = needle.charAt(length-k-1) + s2; // s2 combines characters from the right to the left
if (s1.equals(s2) && s1.length()!=length) {
result = Math.max(s1.length(), result); //If s1 equals s2, we take down their length
}
}

return result;

}``````

• Man, you don't really understand KMP algorithm do you??
KMP uses a table to record the number of steps that can be skipped for the scanner pointer. It processes the needle and generates the table once for all. That's basically the source of its swiftness.
However, your implementation calls the "step" function every time the match fails, it causes O(N^2).

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