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 S[l,r].

Attantion, each same palindromic substring can only be counted once.

 

Input

First line contains T denoting
the number of testcases.

T testcases
follow. For each testcase:

First line contains a string S.
We ensure that it is contains only with lower case letters.

Second line contains a interger Q,
denoting the number of queries.

Then Q lines
follow, In each line there are two intergers l,r,
denoting the substring which is queried.

1≤T≤10, 1≤length≤1000, 1≤Q≤100000, 1≤l≤r≤length

 

Output

For each testcase, output the answer in Q lines.

 

Sample Input

1

abba

2

1 2

1 3

 

Sample Output

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;

}