Palindrome Properties

Distinct Palindromic Substrings

A string of length n contains at most n distinct palindromic substrings.

Proof: For each position i, consider its longest palindromic suffix (red segment). Other palindromic suffixes (blue segments) must have appeared earlier in the string due to palindrome symmetry.

Border and Period Relationships

1. A string s with length n has a border of length x if and only if it has a period of length n-x.

Proof: The matching segments on both sides demonstrate periodicity.

2. Weak Periodicity Lemma: If p and q (p ≠ q, p+q ≤ n) are both periods of s, then gcd(p,q) is also a period.

Manacher's Algorithm

Computes the longest palindromic substring in O(n) time by maintaining a rightmost palindrome boundary [L,R] and leveraging symmetry.

void manacher(const string &s) {
    string t = "#";
    for(char c : s) t += c, t += '#';
    
    vector<int> p(t.size());
    int center = 0, right = 0;
    
    for(int i = 1; i < t.size()-1; i++) {
        int mirror = 2*center - i;
        if(i < right) p[i] = min(right-i, p[mirror]);
        
        while(t[i+(1+p[i])] == t[i-(1+p[i])]) p[i]++;
        
        if(i+p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
}

Palindrome Automaton (PAM)

Constructs all distinct palindromic substrings in linear time with nodes representing equivalence classes.

struct PAM {
    struct Node {
        int len, fail;
        map<char,int> next;
    };
    vector<Node> nodes;
    int last;
    
    PAM() {
        nodes.push_back({-1,0,{}}); // odd root
        nodes.push_back({0,0,{}});   // even root
        last = 1;
    }
    
    void extend(const string &s, int i) {
        char c = s[i];
        int p = last;
        while(s[i-nodes[p].len-1] != s[i]) p = nodes[p].fail;
        
        if(!nodes[p].next.count(c)) {
            int fail = nodes[p].fail;
            while(s[i-nodes[fail].len-1] != s[i]) fail = nodes[fail].fail;
            
            nodes.push_back({
                nodes[p].len + 2,
                nodes[fail].next[c],
                {}
            });
            nodes[p].next[c] = nodes.size()-1;
        }
        last = nodes[p].next[c];
    }
};

Suffix Automaton (SAM)

Linear-size automaton capturing all sufffixes of a string with powerful substring operations.

struct SAM {
    struct State {
        int len, link;
        map<char,int> next;
    };
    vector<State> st;
    int last;
    
    SAM() {
        st.push_back({0,-1,{}});
        last = 0;
    }
    
    void extend(char c) {
        int p = last;
        st.push_back({st[p].len+1,0,{}});
        int curr = st.size()-1;
        
        while(p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = curr;
            p = st[p].link;
        }
        
        if(p == -1) {
            st[curr].link = 0;
        } else {
            int q = st[p].next[c];
            if(st[p].len+1 == st[q].len) {
                st[curr].link = q;
            } else {
                int clone = st.size();
                st.push_back({st[p].len+1,st[q].link,st[q].next});
                while(p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[curr].link = clone;
            }
        }
        last = curr;
    }
};

Applications

1. Substring Search: Check if pattern exists in text in O(m) time

2. Longest Common Substring: Between two strings in O(n+m)

3. Distinct Substrings: Count is sum of (len[u]-len[link[u]]) for all states

4. Lexicographical Order: Traverse SAM to enumerate substrings in order