x. Palindromes and Manacher

The recurring difficulty is the odd/even distinction, which every technique handles in its own way. Manacher gives the maximal palindrome around every centre in $O(n)$ (the same mirror-and-extend skeleton as the Z-function); hashing gives $O(1)$ palindrome tests; the eertree handles distinct palindromes and factorisations.

Task	Method	Cost
is $s[l..r)$ a palindrome	Manacher lookup, or forward/reverse hashes	$O(1)$
longest palindromic substring	Manacher; or hashing + binary search per centre	$O(n)$; $O(n\log n)$
count palindromic substrings with multiplicity	${\sum }_c\lceil {\mathrm{len}}_c/2\rceil$ over centres	$O(n)$
count palindromic substrings of $s[l..r)$, online	Manacher + wavelet trees (“sum of min”)	$O(\log n)$ per query
count distinct palindromes; occurrences of each	eertree	$O(n)$
longest palindromic subsequence; min insertions	LCS with the reverse; $n-\mathrm{LPS}$	$O(n^2)$
minimum cuts into palindromes	$O(n^2)$ DP with the palindrome test; $O(n\log n)$ with series links
shortest palindrome by prepending / appending	prefix function of $s\#\mathrm{rev}(s)$ / $\mathrm{rev}(s)\#s$	$O(n)$
palindromic pairs among words	hash each word and its reverse, match	$O(\sum |w|)$
rearrangement into a palindrome	at most one character with odd count	$O(n)$

Facts. A string has at most $n$ distinct palindromic substrings (aaa...a has $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$ with multiplicity but only $n$ distinct). The palindromic suffixes of a string form $O(\log n)$ arithmetic progressions by length, which makes the $O(n\log n)$ factorisation possible. The hashing approach generalises to variants Manacher cannot express (one mismatch allowed, weighted palindromes).

struct Manacher {                                           // len[c]: longest palindrome at centre c (0..2n-2; even c = char, odd c = gap)
    vector<int> len;
    template <class T> Manacher(const T& s) {
        int n = sz(s), m = 2 * n + 1; vector<int> rad(m);   // virtual string "#s0#s1#...#": odd p is s[p/2]
        for (int p = 0, c = 0, r = 0; p < m; p++) {
            int k = p < r ? min(rad[2 * c - p], r - p) : 0;
            while (p - k - 1 >= 0 && p + k + 1 < m && ((p - k - 1) % 2 == 0 || s[(p - k - 1) / 2] == s[(p + k + 1) / 2])) k++;
            rad[p] = k; if (p + k > r) c = p, r = p + k;
        }
        len.resize(max(2 * n - 1, 0)); for (int c = 0; c < sz(len); c++) len[c] = rad[c + 1];
    }
    bool isPalindrome(int l, int r) const { return l >= r || len[l + r - 1] >= r - l; }   // s[l, r)
    pair<int, int> longest() const { int best = 0, from = 0; for (int c = 0; c < sz(len); c++) if (len[c] > best) best = len[c], from = (c + 1 - len[c]) / 2; return {from, from + best}; }
    ll count() const { ll r = 0; for (int x : len) r += (x + 1) / 2; return r; }
};
int minPalindromeCuts(const string& s) {                    // fewest palindromes covering s, O(n^2)
    int n = sz(s); Manacher m(s); vector<int> dp(n + 1, INT_MAX); dp[0] = 0;
    for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) if (dp[j] != INT_MAX && m.isPalindrome(j, i)) dp[i] = min(dp[i], dp[j] + 1);
    return dp[n];
}

Proof: Manacher

In the virtual string with separators every palindrome has odd length and a unique centre $p$; a palindrome of the original string of length $L$ appears with radius $L$ around $p$ (separators match separators, characters match characters). If $[c-r^{\prime },c+r^{\prime }]$ is the palindrome reaching furthest right ($r=c+r^{\prime }$) and $p<r$, the mirror $2c-p$ sees the same characters within the window, so $\mathrm{rad}[p]\ge \min (\mathrm{rad}[2c-p],r-p)$, and only comparisons beyond $r$ are needed; each successful comparison pushes $r$ right, so the total is $O(n)$. With len[c] = rad[c + 1], the centre index $c=l+r-1$ of $s[l,r)$ makes isPalindrome a radius check. Counting: around a centre with maximal length $L$, the palindromes are those of lengths $L,L-2,\dots$ of the right parity, $\lceil L/2\rceil$ of them. Cuts DP: the last piece of an optimal cover is a palindrome $s[j,i)$. Verified by brute force.

Palindromic substrings of a range

Number of palindromic substrings (by position) of $s[l,r)$, online. An odd centre $i$ with radius $R_i$ (number of odd palindromes there) contributes $\min (R_i,i-l+1,r-i)$; left of the middle of $[l,r)$ the second term is the binding one, right of it the third. With $A_i=R_i-i$: ${\sum }_{i\le m}\min (R_i,i-l+1)={\sum }_{i}i+{\sum }_i\min (A_i,1-l)$, a “sum of minimum with a constant” over a range, answered by a wavelet tree with prefix sums; symmetrically on the right with $R_i+i$, and the same for even centres. Uses a wavelet tree (full version, also with $k$-th smallest, counting equal values and adjacent swaps, as in Range Order Statistics).

template <class T> struct WaveletTree {
    struct Node { int lo = 0, hi = 0, left = -1, right = -1; vector<int> b; vector<T> c; };   // b[i]: #first i going left; c[i]: sum of first i
    int n; vector<T> vals; vector<int> a; vector<Node> t;
    WaveletTree(const vector<T>& arr) : n(sz(arr)), vals(arr) {
        sort(all(vals)); vals.erase(unique(all(vals)), vals.end()); a.resize(n);
        for (int i = 0; i < n; i++) a[i] = lower_bound(all(vals), arr[i]) - vals.begin();
        vector<int> seq = a; build(seq, 0, max<int>(0, sz(vals) - 1));
    }
    int build(vector<int>& seq, int lo, int hi) {
        int id = sz(t); t.emplace_back(); Node nd; nd.lo = lo, nd.hi = hi; int mid = (lo + hi) / 2;
        nd.b.assign(sz(seq) + 1, 0); nd.c.assign(sz(seq) + 1, T{});
        for (int i = 0; i < sz(seq); i++) nd.b[i + 1] = nd.b[i] + (seq[i] <= mid), nd.c[i + 1] = nd.c[i] + vals[seq[i]];
        if (lo < hi && !seq.empty()) {
            vector<int> L, R; for (int x : seq) (x <= mid ? L : R).push_back(x);
            seq.clear(); seq.shrink_to_fit();
            nd.left = build(L, lo, mid); nd.right = build(R, mid + 1, hi);
        }
        t[id] = move(nd); return id;
    }
    T kth(int l, int r, int k) const {                      // k-th smallest (0-indexed) in [l, r)
        int u = 0;
        while (t[u].lo < t[u].hi) {
            const Node& nd = t[u]; int inLeft = nd.b[r] - nd.b[l];
            if (k < inLeft) l = nd.b[l], r = nd.b[r], u = nd.left; else k -= inLeft, l -= nd.b[l], r -= nd.b[r], u = nd.right;
        }
        return vals[t[u].lo];
    }
    pair<int, T> rankSum(int u, int l, int r, int x) const {   // count and sum of compressed values <= x in [l, r)
        if (u < 0 || l >= r || x < t[u].lo) return {0, T{}};
        const Node& nd = t[u]; if (nd.hi <= x) return {r - l, nd.c[r] - nd.c[l]};
        auto [c1, s1] = rankSum(nd.left, nd.b[l], nd.b[r], x); auto [c2, s2] = rankSum(nd.right, l - nd.b[l], r - nd.b[r], x);
        return {c1 + c2, s1 + s2};
    }
    int compressUpper(const T& x) const { return upper_bound(all(vals), x) - vals.begin() - 1; }
    int countLessEq(int l, int r, const T& x) const { return vals.empty() ? 0 : rankSum(0, l, r, compressUpper(x)).first; }
    T sumLessEq(int l, int r, const T& x) const { return vals.empty() ? T{} : rankSum(0, l, r, compressUpper(x)).second; }
    int countEqual(int l, int r, const T& x) const {
        auto it = lower_bound(all(vals), x); if (it == vals.end() || *it != x) return 0;
        int c = it - vals.begin(); return rankSum(0, l, r, c).first - (c ? rankSum(0, l, r, c - 1).first : 0);
    }
    void swapAdjacent(int i) {                              // swap a[i], a[i+1] in O(log)
        int x = a[i], y = a[i + 1], u = 0, p = i;
        while (true) {
            Node& nd = t[u]; nd.c[p + 1] = nd.c[p] + vals[y];
            if (nd.lo == nd.hi) break;
            int mid = (nd.lo + nd.hi) / 2; bool gx = x <= mid, gy = y <= mid;
            if (gx != gy) { nd.b[p + 1] = nd.b[p] + gy; break; }
            if (gx) p = nd.b[p], u = nd.left; else p = p - nd.b[p], u = nd.right;
        }
        swap(a[i], a[i + 1]);
    }
};
struct PalindromesInRange {
    int n; vector<ll> A, B, C, D; WaveletTree<ll> wa, wb, wc, wd;   // odd: R - i, R + i; even (centre before i): E - i, E + i
    template <class S> static vector<ll> build(const S& s, int kind) {
        Manacher m(s); int n = sz(s); vector<ll> v(n, 0);
        for (int i = 0; i < n; i++) {
            if (kind < 2) { ll R = (m.len[2 * i] + 1) / 2; v[i] = kind == 0 ? R - i : R + i; }
            else { ll E = i > 0 ? m.len[2 * i - 1] / 2 : 0; v[i] = kind == 2 ? E - i : E + i; }
        }
        return v;
    }
    template <class S> PalindromesInRange(const S& s) : n(sz(s)), A(build(s, 0)), B(build(s, 1)), C(build(s, 2)), D(build(s, 3)), wa(A), wb(B), wc(C), wd(D) {}
    static ll sumMin(const WaveletTree<ll>& w, int l, int r, ll x) { if (l >= r) return 0; ll le = w.countLessEq(l, r, x); return w.sumLessEq(l, r, x) + x * ((r - l) - le); }
    static ll sumIdx(ll l, ll r) { return l < r ? (l + r - 1) * (r - l) / 2 : 0; }
    ll query(int l, int r) const {                          // palindromic substrings s[a, b) with l <= a < b <= r
        if (l >= r) return 0;
        ll res = 0; int m1 = (l + r - 1) / 2;               // odd centres i <= m1: min(R, i - l + 1)
        res += sumIdx(l, m1 + 1) + sumMin(wa, l, m1 + 1, 1 - l);
        res += -sumIdx(m1 + 1, r) + sumMin(wb, m1 + 1, r, r);
        int m2 = (l + r) / 2, lo = l + 1, hi = r;           // even centres i in [l+1, r-1]: min(E, i - l, r - i)
        if (lo < hi) { int mid = min(max(m2 + 1, lo), hi); res += sumIdx(lo, mid) + sumMin(wc, lo, mid, -l); res += -sumIdx(mid, hi) + sumMin(wd, mid, hi, r); }
        return res;
    }
};

Proof: the range-count decomposition and the wavelet tree

An odd centre $i$ supports $R_i$ odd palindromes (radii $\mathrm{0..}{R}_i-1$); inside $[l,r)$ the radius is also limited by $i-l$ and $r-1-i$, so the count is $\min (R_i,i-l+1,r-i)$. For $i\le m_1=\lfloor \frac{l+r-1}{2}\rfloor$, $i-l+1\le r-i$, so the count is $\min (R_i,i-l+1)=i+\min (R_i-i,1-l)$; for $i>m_1$ it is $-i+\min (R_i+i,r)$. Even centres between $i-1$ and $i$ with $E_i$ palindromes behave the same with $\min (E_i,i-l,r-i)$ and split point $\lfloor \frac{l+r}{2}\rfloor$. Each term ${\sum }_{i\in [a,b)}\min (v_i,x)$ equals (sum of values $\le x$) $+x\cdot$(count of values $>x$). Wavelet tree: each level partitions the values by the midpoint of the value range and stores prefix counts and sums, so a range splits into $O(\log )$ canonical pieces; kth descends by comparing $k$ with the number going left; swapAdjacent only changes the prefix arrays at one position on the levels where both elements still share a node. Verified against brute force for all ranges of random strings.

Related notes

• Eertree
• Prefix Function and Z (shortest palindrome by appending)
• Hashing (palindrome hashes)