Queries for Number of Palindromes

题目描述

给你一个字符串s由小写字母组成，有q组询问，每组询问给你两个数，l和r，问在字符串区间l到r的字串中，包含多少回文串。

输入格式

第1行，给出s，s的长度小于5000
第2行给出 $q \ (1 <= q <= 10^6)$

分析

对于每次询问，暴力求解的时间复杂度肯定不行。

注意到字符串的长度不是很大，考虑预处理每一个区间的回文串个数。

设 $f[i][j],\ g[i][j]$ 分别表示区间 $[l, r]$ 是否是回文串和其所有子区间的回文串总和。

$f[i][j]$ 的很好处理， 思考 $g[i][j]$ 的转移，发现其本质上是一个二维前缀和的问题：

  • $g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1]$

而对于 $f[i][j]$ ，枚举每一个回文中心，向两边拓展，注意长度的奇偶性。

1
2
3
4
for (int i = 1; i <= n; i++){
    for (int l = i, r = i; l && r <= n && s[l] == s[r]; l--, r++) f[l][r] ++;
    for (int l = i, r = i + 1; l && r <= n && s[l] == s[r]; l--, r++) f[l][r] ++;
}

初始时， $g[i][i] = f[i][i]$，其实 $g \ , f$ 可以合并到一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 5;

int n, q;
int dp[N][N];

char s[N];

signed main(){
    
    scanf("%s", s + 1); n = strlen(s + 1);
    
    for (int i = 1; i <= n; i++){
        for (int l = i, r = i; l && r <= n && s[l] == s[r]; l--, r++) dp[l][r] ++;
        for (int l = i, r = i + 1; l && r <= n && s[l] == s[r]; l--, r++) dp[l][r] ++;
    }
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    
    scanf("%d", &q);
    
    for (int l, r; q--; ){
        scanf("%d%d", &l, &r);
        printf("%d\n", dp[r][r] - dp[r][l - 1] - dp[l - 1][r] + dp[l - 1][l - 1]);
    }
    
    return 0;
}

Written with StackEdit中文版.