0ms C version, KMP with reverse-order matching, get max prefix palindrome


  • 1
    G
    //0ms, O(n), KMP
    char* shortestPalindrome(char* s) {
        if (!s || !*s) return strdup("");
        const int N = strlen(s);
        const int HN = (N >> 1);
        int pi[HN], k, i, ch;
    
        // Get prefix array
        k = pi[0] = 0;
        for (i = 1; i < HN; i++) {
            ch = s[i];
            while ((k > 0) && (ch != s[k])) k = pi[k - 1];
            if (ch == s[k]) k++;
            pi[i] = k;
        }
    
        // Match in reverse order
        for (i = N - 1, k = 0; i >= k; i--) {
            ch = s[i];
            while ((k > 0) && (ch != s[k])) k = pi[k - 1];
            if (ch == s[k]) k++;
        }
    
        // Finally, only (N - i - k - 1) chars need to be added to make the shortest palindrome
        int len = N - (i + k);
        char* ret = (char*)malloc((len + N)* sizeof(char));
        if (ret != NULL) {
            char* p = ret;
            for (i = N - 1; i > N - len; i--) *p++ = s[i];
            strcpy(p, s);
        }
    
        return ret;
    }

Log in to reply
 

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