NSOqwq

题解 CF245H 【Queries for Number of Palindromes】

题解 CF245H 【Queries for Number of Palindromes】


简化题意

给定一个字符串 $s$,$q$ 次询问 $[l,r]$ 区间内的回文子串个数。

数据规模:$\left|s\right| \le 5\times 10^3$,$q \le 10^6$。


DP 分析

先看一下一个经常遇到的问题:询问区间 $[l,r]$ 是否是回文子串。

设 $f(l,r)$ 为 $[l,r]$ 是否是回文子串。

$$ f(l,r) = \begin{cases} 1 & f(l+1,r-1) \text{ and } (s_l=s_r) \\ 0 & otherwise. \end{cases} $$

如果是双字符的话会导致 $l+1>r-1$,提前处理一下双字符和单字符子串就行了。

由于是从小区间 $[l+1,r-1]$ 推到大区间 $[l,r]$,那么就需要区间 dp 的写法,从区间长度为 $3$ 开始 dp,因为已预处理双字符和单字符。

那么,如何类似地,求解这个区间内回文子串个数的问题呢?

设 $g(l,r)$ 为 $[l,r]$ 内回文子串个数。

$$ g(l,r) = g(l+1, r) + g(l, r-1) - g(l+1, r-1) + f(l, r) $$

也就是说,分别考虑左边、右边的小区间,减去中间的区间,再加上最终大区间是否是回文串就行了。

区间 dp 的方式计数即可。可以先预处理对于所有的 $i$,$g(i, i) = 1$,剩下的从区间长度为 $2$ 开始 dp。

这里的 $g(l,r)$ 也可以被看作二维前缀和。

核心实现

int main() {
    scanf("%s", s + 1); // 字符串下标从 1 开始方便 dp。
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) {
        f[i][i] = true, g[i][i] = 1; // 单字符预处理。
        if (i >= 2)
            f[i - 1][i] = (s[i] == s[i - 1]); // 双字符预处理。
    }
    for (int len = 3; len <= n; ++len)
        for (int l = 1; l <= n - len + 1; ++l) {
            const int r = l + len - 1;
            f[l][r] = f[l + 1][r - 1] && (s[l] == s[r]);
        }
    for (int len = 2; len <= n; ++len)
        for (int l = 1; l <= n - len + 1; ++l) {
            const int r = l + len - 1;
            g[l][r] = g[l + 1][r] + g[l][r - 1] - g[l + 1][r - 1] + f[l][r];
        }
    q = read();
    while (q--) {
        int l = read(), r = read();
        printf("%d\n", g[l][r]);
    }
    return 0;
}

2021-07-28 13:28:48 in 题解