# Why KMP get TLE with large test case

• case: "aaaaaaaaaaaaaaaaaaaaaaaaa....aaaaaaaaaab", and my code get TLE

``````public String strStr(String haystack, String needle) {
if (needle == null || haystack == null
|| needle.length() > haystack.length())
return null;
if (needle.length() == 0)
return haystack;
int[] partialMatchTable = calculatePartialMatchTable(needle);
for (int i = 0; i <= haystack.length() - needle.length();) {
if (haystack.charAt(i + needle.length() - 1) != needle
.charAt(needle.length() - 1)) {
i++;
continue;
}
int k = 0;
for (; k < needle.length(); k++) {
if (needle.charAt(k) != haystack.charAt(i + k))
break;
}
if (k == needle.length())
return haystack.substring(i);
else
i += k + 1 - partialMatchTable[k];
}
return null;
}

public int[] calculatePartialMatchTable(String needle) {
int[] partialMatchTable = new int[needle.length()];
for (int i = 0; i < needle.length(); i++) {
partialMatchTable[i] = 0;
for (int j = 1; j <= i; j++) {
for (int k = 0; k <= j; k++) {
if (k == j) {
partialMatchTable[i] = j;
break;
}
if (needle.charAt(k) != needle.charAt(i - j + k + 1))
break;
}
}
}
return partialMatchTable;
}``````

• calculatePartialMatchTable takes too muck time. There is a O(n) solution to this function and you used a O(n^3) algorithm

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