C++ modified KMP O(n) time & memory


  • 0
    M

    The basic idea to build a KMP failure function on the reverse string r of the given string s. The modification from KMP is, when building the failure function and looking for the next partial match, instead of comparing the characters in the same string, we compare the characters in the reverse against the original string. So, the meaning of the failure function also changed. At each index, the value means the length of the longest suffixes (of reverse string r) that equals to the prefix of the original string s.

        string shortestPalindrome(string s) {
            string r = s;
            reverse(r.begin(), r.end());
            if (s == r) return s;
            vector<int> kmp(r.length()+1, 0);
            for (uint i=2; i<kmp.size(); i++) {
                int j = i-1;
                do { j = kmp[j]; }
                while (j && s[j] != r[i-1]);
                kmp[i] = (s[j] == r[i-1]) ? (j+1) : 0;
            }
            return r.substr(0, r.length()-kmp.back()) + s;
        }
    

Log in to reply
 

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