[CF245H]Queries for Number of Palindromes


luogu

sol

显然\(Q\)那么大而\(n\)又那么小就一定是\(O(n^2)\)预处理然后每个询问\(O(1)\)回答就好了。
枚举每个起点然后一个一个往后面插入。
所有的回文子串的个数?
记录一下回文树上的\(dep\),那么每插入一个字符以后新增的贡献就是\(last\)节点的\(dep\)值。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi()
{
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 5005;
struct Palindromic_Tree{
    int tr[N][26],fa[N],len[N],dep[N],last,tot;
    void init()
        {
            memset(tr,0,sizeof(tr));
            memset(fa,0,sizeof(fa));
            memset(len,0,sizeof(len));
            memset(dep,0,sizeof(dep));
            fa[last=0]=fa[1]=1;len[tot=1]=-1;
        }
    void extend(int c,int n,char *s)
        {
            int v=last;
            while (s[n-len[v]-1]!=s[n]) v=fa[v];
            if (!tr[v][c])
            {
                int u=++tot,k=fa[v];
                len[u]=len[v]+2;
                while (s[n-len[k]-1]!=s[n]) k=fa[k];
                fa[u]=tr[k][c];tr[v][c]=u;
                dep[u]=dep[fa[u]]+1;
            }
            last=tr[v][c];
        }
}T;
char s[N],ch[N];int ans[N][N];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    for (int i=1;i<=n;++i)
    {
        T.init();
        for (int j=i;j<=n;++j) ch[j-i+1]=s[j];
        for (int j=i;j<=n;++j)
        {
            T.extend(ch[j-i+1]-'a',j-i+1,ch);
            ans[i][j]=ans[i][j-1]+T.dep[T.last];
        }                                    
    }
    int q=gi();
    while (q--)
    {
        int l=gi(),r=gi();
        printf("%d\n",ans[l][r]);
    }
    return 0;
}
智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告