12ms O(n) solution using palindrome tree (NOT KMP)


  • 0
    A

    In this problem, we simply want to know the longest prefix palindrome substring of s. For example, s = "aabba", "aa" is the one we need to know and we only need to patch "abb" in front of s. Here I want to introduce another very powerful and general data structure that can solve many questions related to palindrome substrings in a string.

    The data structure is called palindrome tree. The nodes in the tree are the longest SUFFIX palindrome substrings in s[0...i] for 0 <= i < n, where n = s.size(). Besides, two additional roots are introduces.

    Each node having A as the palindrome, has the length (A.size()), suffix links which points to the longest proper suffix palindrome substring of itself, and the out going edges (each edge is labeled with a char x and points to another palindrome node xAx, where A is the palindrome of the node itself). Regarding the two additional roots, one is empty string and its suffix link points to another root. The other one is a pseudo string having length -1 and has no suffix link. (You will see why in the code)

    To build up the tree, you need to process the string char by char from s[0] to s[n-1]. When processing s[i], we start from the palindrome node A, which is the longest suffix palindrome in s[0...i-1]. We check if s[i] == s[i - A.size() - 1]. If so, we can extend A to xAx, otherwise we go to node pointed by A's suffix link and repeat the check until either we could extend at some node or we hit the root node with -1 length. Let the found node be B. We could easily check if the palindrome is already existed by looking at the B's outgoing edges. If it is not existed, we create a new one and draw an edge from B to the new node with label s[i], then we continue to find B's longest suffix palindrome that can be extended at both side with s[i] and make the suffix link of the new node pointing to the found node; otherwise, do nothing. Finally, we update the last pointer to point the longest suffix palindrome node in s[0...i]. Therefore, to compute the longest prefix palindrome substring, we simply reverse s and process char by char to the end. The longest suffix palindrome of s.reverse() is the one we need. It is not hard to prove that the size of the tree is O(n) and its time complexity is also O(n).

    Compare to KMP, we don't need to add another string to do a trick. It is straightforward. Besides, it can answer so many palindrome substring problems. For more detail, please refer to :
    http://adilet.org/blog/25-09-14/
    http://www.geeksforgeeks.org/palindromic-tree-introduction-implementation/

    struct PalindromeNode {
        unordered_map<char, PalindromeNode*> out;
        PalindromeNode* suffix;
        int len;
        PalindromeNode(int l) : len(l), suffix(NULL) {}; 
    };
    
    class Solution {
    public:
        int findLongestSuffixPalindrome(string& s) {
            PalindromeNode* root1 = new PalindromeNode(0);
            PalindromeNode* root2 = new PalindromeNode(-1);
            root1->suffix = root2; 
            PalindromeNode* last = root1;
            for (int i = 0; i < s.size(); i++) {
                int j = i - last->len - 1;
                while ((j < 0) || (s[j] != s[i])) {
                    last = last->suffix;
                    j = i - last->len - 1;
                }
                if (last->out.find(s[i]) == last->out.end()) {
                    PalindromeNode* node = new PalindromeNode(last->len + 2);
                    last->out[s[i]] = node;
                    //Find suffix link for the new node
                    last = last->suffix;
                    if (last == NULL) {
                        //node is a single char
                        node->suffix = root1;
                    } else {
                        while ((last->suffix != NULL )) {
                            j = i - last->len - 1;
                            if (s[j] == s[i]) {
                                break;
                            }
                            last = last->suffix;
                        }
                        node->suffix = last->out[s[i]];
                    }
                    last = node;
                } else {
                    last = last->out[s[i]];
                }
            }
            return last->len;
        }
        
        string shortestPalindrome(string s) {
            if (s.size() == 0) {
                return s;
            }
            string t = s;
            reverse(t.begin(), t.end());
            int prefixPalLen = findLongestSuffixPalindrome(t);
            s = string(t.begin(), t.end() - prefixPalLen) + s;
            return s;
        }
    };
    

Log in to reply
 

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