CF245H Queries for Number of Palindromes

题目描述

给出一个字符串和\(q\)次询问，对每次询问求出区间\(l,r\)间回文子串的个数。

输入格式

略

输出格式

每行对一个询问输出一个答案。

数据范围分析

\(|s|\le5000;\)

\(q\le10^6;\)

可以\(n^2\)预处理。

code

#include<bits/stdc++.h>
char s[5001]; 
int n,q,f[5001][5001];
int main()
{
    scanf("%s%d",s+1,&q);
    n=strlen(s+1);
    for(register int i=1;i<=n;i=-~i)
        f[i][i]=1;
    for(register int i=1,j=i,k=i;i<=n;i=-~i,j=i,k=i)
        while(--j&&(k=-~k)<=n&&!(s[j]^s[k]))
            f[j][k]=1;
    for(register int i=1,j=i,k=-~i;i<=n;i=-~i,j=i,k=-~i)
        while(j&&k<=n&&!(s[j]^s[k]))
        {
            f[j][k]=1;
            --j;
            k=-~k;
        }
    
    for(register int i=1;i<=n;i=-~i)
        for(register int j=1;j<=n;j=-~j)
            f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",(f[r][r]-f[l-1][r]-f[r][l-1]+f[l-1][l-1])/2);
    }
    
    return 0;
}

solution

\(n\)很小，可以先\(n^2\)找出所有子串，并在一个二维数组中标记回文串。

怎么找？可以枚举串的中点（或中点左边的字符），然后用两个变量同时从中点开始向左右两边移动。如当前两变量所处字符相等则标记为回文串并继续移动，否则直接退出循环。

如这个串：acaaaba

假设当前我们枚举到了第四位。单个字符必为回文串，故标记\(f[4][4]=1\)。

然后\(j=3,k=5\)。发现\(s[j]==s[k]\)。标记\(f[3][5]=1\)。继续移动。

然而发现\(s[2]!=s[6]\)。显然继续扩展也不可能得到回文串了，故退出循环。

刚才枚举的是长度为奇数的串，此时令\(j=4,k=5\)。发现\(s[4]==s[5]\)而\(s[3]!=s[6]\)。以此类推在\(f\)数组中标记所有回文串。

然后呢？

怎么对一个\([l,r]\)区间求回文串个数？

容易发现这个区间的子串的左右端点分别大于等于\(l\)，小于等于\(r\)。从\(l\)到\(r\)双重循环一遍？显然超时。

我们要求的是所有回文子串的数量，不妨设所有子串中回文的价值为\(1\)，否则为\(0\)。这恰好是我们处理出的\(f\)数组。则问题转化为：求

\(\sum_{i=l}^r\sum_{j=l}^rf[i][j]\)。

快速求解上式，不过一个二维前缀和而已。

时间复杂度\(O(n^2+q)\)。