Why KMP get TLE with large test case


  • 0
    T

    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;
    }

  • 0
    H

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


Log in to reply
 

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