codeforces 245H Queries for Number of Palindromes RK Hash + dp

H. Queries for Number of Palindromes

time limit per test

5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You've got a string s = s1s2... s|s| of length |s|, consisting of lowercase English letters. There also are qqueries, each query is described by two integers li, ri (1 ≤ li ≤ ri ≤ |s|). The answer to the query is the number of substrings of string s[li... ri], which are palindromes.

String s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) is a substring of string s = s1s2... s|s|.

String t is called a palindrome, if it reads the same from left to right and from right to left. Formally, if t = t1t2... t|t| = t|t|t|t| - 1... t1.

Input

The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 106)— the number of queries. Next q lines contain the queries. The i-th of these lines contains two space-separated integers li, ri (1 ≤ li ≤ ri ≤ |s|) — the description of the i-th query.

It is guaranteed that the given string consists only of lowercase English letters.

Output

Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

Examples

input

Copy

caaaba
5
1 1
1 4
2 3
4 6
4 5

output

Note

Consider the fourth query in the first test case. String s[4... 6] = «aba». Its palindrome substrings are: «a», «b», «a», «aba».

大意：长度为N的字符串，Q个询问，询问某个区间中回文子串（连续）的数量

题解：

将字符串和反转串的RK hash值求出，这样可以O(1)判断两个子串是否相等。

f[i][j]表示[i,j]区间中回文子串的数量，可以以区间大小为阶段利用简单容斥来递推。

f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+([i,j]是回文串)

要[i,j]是回文串，只需在原串中求出前半部分的 hash 值，在反转串中求出后半串的 hash 值，判断是否相等即可。

tips：亲测O(N^2 logN)过不了，要预处理seed的幂次方

 /*

 Welcome Hacking

 Wish You High Rating

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<ctime>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<string>

 using namespace std;

 int read(){

     int xx=,ff=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 const int seed[]={,},MOD=;

 char s1[],s2[];

 int H1[][],H2[][];

 int N;

 int pow_seed[][];

 void Hashing(int x){

     for(int i=;i<=N;i++){

         H1[x][i]=(1LL*H1[x][i-]*seed[x]+s1[i])%MOD;

         H2[x][i]=(1LL*H2[x][i-]*seed[x]+s2[i])%MOD;

     }

 }

 int get_hash1(int x,int L,int R){

     return ((H1[x][R]-1LL*H1[x][L-]*pow_seed[x][R-L+])%MOD+MOD)%MOD;

 }

 int get_hash2(int x,int L,int R){

     return ((H2[x][R]-1LL*H2[x][L-]*pow_seed[x][R-L+])%MOD+MOD)%MOD;

 }

 inline int ref(int x)

 {return N-x+;}

 inline bool judge(int L,int R){

     if(L==R)

         return ;

     int mid=(L+R)/;

     if((R-L+)%==){

         if(get_hash1(,L,mid)==get_hash2(,ref(R),ref(mid+)))

             if(get_hash1(,L,mid)==get_hash2(,ref(R),ref(mid+)))

                 return ;

     }

     else{

         if(get_hash1(,L,mid)==get_hash2(,ref(R),ref(mid)))

             if(get_hash1(,L,mid)==get_hash2(,ref(R),ref(mid)))

                 return ;

     }

     return ;

 }

 long long f[][];

 int main(){

     //freopen("in","r",stdin);

     gets(s1+);N=strlen(s1+);

     for(int i=;i<=N;i++)

         s2[i]=s1[ref(i)];

     pow_seed[][]=pow_seed[][]=;

     for(int i=;i<=N;i++){

         pow_seed[][i]=1LL*pow_seed[][i-]*seed[]%MOD;

         pow_seed[][i]=1LL*pow_seed[][i-]*seed[]%MOD;

     }

     Hashing();

     Hashing();

     for(int i=;i<=N;i++)

         f[i][i]=;

     for(int p=;p<=N;p++)

         for(int i=;i<=N;i++){

             int j=i+p-;

             if(j>N)

                 break;

             f[i][j]=f[i+][j]+f[i][j-]-f[i+][j-]+judge(i,j);

         }

     /*for(int i=1;i<=N;i++){

         for(int j=1;j<=N;j++)

             printf("%I64d ",f[i][j]);

         puts("");

     }*/

     for(int Q=read();Q;Q--){

         int t1=read(),t2=read();

         printf("%I64d\n",f[t1][t2]);

     }

     return ;

 }

巴特西

codeforces 245H Queries for Number of Palindromes RK Hash + dp

最新文章

热门文章