manacher

简介

贴个板子

struct Manacher {
    int n, l, f[maxn * 2], Len; 
    char s[maxn * 2]; 

    void init(char *c) {
        l = strlen(c + 1); s[0] = '~'; 
        for (int i = 1, j = 2; i <= l; ++i, j += 2)
            s[j] = c[i], s[j - 1] = '#';
        n = 2 * l + 1; s[n] = '#'; s[n + 1] = '\0';
    }
    void manacher() {
        int p = 0, mr = 0;
        for (int i = 1; i <= n; ++i) f[i] = 0;
        for (int i = 1; i <= n; ++i) {
            if (i < mr) f[i] = min(f[2 * p - i], mr - i);
            while (s[i + f[i]] == s[i - f[i]]) ++f[i]; --f[i];
            if (f[i] + i > mr) mr = i + f[i], p = i;
            Len = max(Len, f[i]); 
        }
    }
    
    void solve() {
        for (int i = 1; i <= n; ++i) {
            // [1, l]
            int L = i - f[i] + 1 >> 1, R = i + f[i] - 1 >> 1;
            if (!f[i]) continue;

            // [1, 2 * l + 1] 
            L = i - f[i], R = i + f[i];
        } 
    }
} M;

例题

简要题意：给定一个长度为 $n$ 的字符串 $S$ 和一个正整数 $k$，求 $S$ 的长度前 $k$ 大的回文子串的长度的积

$n\le 10^6,k\le 10^{12}$

简要题解：直接用 $manacher$ 求出每个回文中心的极大回文长度，用这个东西即可求出长度为 $i$ 的回文子串的个数

Luogu P1659 [国家集训队]拉拉队排练
简要题解：给定一个字符串 $S$，求 $S$ 有多少前缀 $T$，满足 $T$ 进行若干次操作后得到的串 $T’$ 存在一个前缀为 $S$，字符串 $S$ 进行一次操作定义为固定 $S$ 的最后一个字符，将剩下的字符翻转并且拼接到 $S$ 的后面，例如 $abcd$ 操作一次后得到 $abcdcba$

$|S|\le 10^6$

简要题解：我们如果前缀 $i$ 合法，那么前缀 $2\times i-1$ 一定也合法，反之亦然，同时对于 $2\times k -1>n$ 的前缀 $k$，$k$ 合法的条件为以 $k$ 为中心的极大回文子串的右端点为 $n$，有这个条件后我们用 $manacher$ 求每个位置作为回文中心的极大回文子串长度然后倒推即可

Luogu P5446 [THUPC2018]绿绿和串串
简要题意：给定字符串 $S$ 和 $T$，其长度分别为 $n$ 和 $m$，$S[l..r]$ 的价值为 $T$ 在 $S[l..r]$ 中的出现次数，求 $S$ 的所有长度为奇数的回文子串的价值和

$n,m\le 3\times 10^6$

简要题解：首先用 $kmp$ 求出 $T$ 在 $S$ 的中所有匹配位置，我们以结束位置来标记

然后用 $manacher$ 求出每个回文中心 $i$ 的极大回文子串的半径 $a_i$，即以 $i$ 为中心的极大回文子串为 $S[i-a_i..i+a_i]$，那么对于一个 $T$ 的匹配位置 $r$，它对以 $i$ 为中心，半径为 $j$ 的产生贡献的条件为 $r\in [i-j+m-1,i+j]$，也就是回文中心 $i$ 的贡献为 $j\in[\lfloor\frac{m}{2}\rfloor,a_i],d_{i+j}-d_{i+m-1-j-1}$，其中 $d$ 是 $T$ 的匹配位置的一阶前缀和数组，容易发现这个贡献的形式显然为 $d$ 的区间查询，我们把 $d$ 再做一次前缀和即可实现对于每个回文中心 $i$，$O(1)$ 计算答案，时间复杂度 $O(n)$

Luogu P6216 回文匹配