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]$ ,枚举每一个回文中心,向两边拓展,注意长度的奇偶性。
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$ 可以合并到一起。
#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;
}
标签:CF245H,int,字符串,区间,长度,回文 From: https://www.cnblogs.com/genshin-player/p/18103661Written with StackEdit中文版.