前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 5658 CA Loves Palindromic(回文树)

HDU 5658 CA Loves Palindromic(回文树)

作者头像
ShenduCC
发布2018-04-26 17:27:28
6640
发布2018-04-26 17:27:28
举报
文章被收录于专栏:算法修养

CA Loves Palindromic

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 301    Accepted Submission(s): 131

Problem Description

CA loves strings, especially loves the palindrome strings. One day he gets a string, he wants to know how many palindromic substrings in the substring . Attantion, each same palindromic substring can only be counted once.

Input

First line contains  denoting the number of testcases.  testcases follow. For each testcase: First line contains a string . We ensure that it is contains only with lower case letters. Second line contains a interger , denoting the number of queries. Then  lines follow, In each line there are two intergers , denoting the substring which is queried.

Output

For each testcase, output the answer in  lines.

Sample Input

代码语言:javascript
复制
1
abba
2
1 2
1 3

Sample Output

代码语言:javascript
复制
2
3求区间内的本质不同的回文串的个数字符串的长度是1000我们可以利用回文树,求出每个区间内不同回文串的个数枚举区间#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int MAX=100000;
const int maxn=1000;
char str[maxn+5];
int sum[maxn+5][maxn+5];
struct Tree
{
    int next[MAX+5][26];
    int num[MAX+5];
    int cnt[MAX+5];
    int fail[MAX+5];
    int len[MAX+5];
    int s[MAX+5];
    int p;
    int last;
    int n;
    int new_node(int x)
    {
        memset(next[p],0,sizeof(next[p]));
        cnt[p]=0;
        num[p]=0;
        len[p]=x;
        return p++;
    }
    void init()
    {
        p=0;
        new_node(0);
        new_node(-1);
        last=0;
        n=0;
        s[0]=-1;
        fail[0]=1;
    }
    int get_fail(int x)
    {
        while(s[n-len[x]-1]!=s[n])
            x=fail[x];
        return x;
    }
    int add(int x)
    {
        x-='a';
        s[++n]=x;
        int cur=get_fail(last);
        if(!(last=next[cur][x]))
        {
            int now=new_node(len[cur]+2);
            fail[now]=next[get_fail(fail[cur])][x];
            next[cur][x]=now;
            num[now]=num[fail[now]]+1;
            last=now;
            return 1;
        }
        cnt[last]++;
        return 0;
    }
    void count()
    {
        for(int i=p-1;i>=0;p++)
            cnt[fail[i]]+=cnt[i];
    }
}tree;
int q;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {

        scanf("%s",str+1);

        int len=strlen(str+1);
        for(int i=1;i<=len;i++)
        {
            tree.init();
            for(int j=i;j<=len;j++)
            {
               tree.add(str[j]);
               sum[i][j]=tree.p-2;
            }
        }
        scanf("%d",&q);
        int l,r;
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&l,&r);
            printf("%d\n",sum[l][r]);
        }
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-05-10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • CA Loves Palindromic
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档