# Up Sky,Mr.Zhu

Time Limit: 3000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 46    Accepted Submission(s): 14

Problem Description Given a string S[0,…n-1],and the length of each palindrome substring in S is less than 20.

Define special string of a palindrome string STR[0,…,n-1] is STR[floor(n/2),…,n-1]

Given L,R and a string T, Query the number of palindrome strings, whose the prefix of special string is T, in S[L,…,R]

ps:floor means the function in C++ language

(No relation between statement and title)

Input There are severval cases,please peocess until EOF.

The first line contains string S.(1<=|S|<=1e5)

The second line is a number q means the number of querys.(1<=q<=1e5)

The next q lines,each line contains two numbers L,R and a string T.(1<=L<=R<=|S|,1<=|T|<=10)

All strings only contain ‘a’,’b’,’c’,’d’ and ‘e’.

Output For each query,you should output the number of palindrome strings which satisfied previous condition in a line.

Sample Input

bceaeedde 5 5 8 e 3 5 e 1 2 a 5 9 d 5 9 de

Sample Output

3 2 0 4 1

Author UESTC

AC代码：

``````import java.io.*;
import java.util.*;

public class Main {
static int nextInt() throws IOException
{
in.nextToken();
return (int)in.nval;
}
static String next() throws IOException
{
in.nextToken();
return in.sval;
}
static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
static int n,m,len,sz,a;
static char[] s;
static char[] ss=new char[200005];
static int[] pp=new int[200005];
static int[] aa=new int[100005];
static int[] bb=new int[100005];
static int[] cc=new int[100005];
static int[] rt=new int[100005];
static int[] ans=new int[100005];
static int[] cnt=new int[100005];
static char[][] tt=new char[100005][];
static int[][] ch=new int[100005][5];
static void Manacher()
{
Arrays.fill(ss,'#');
for(int i=0;i<n;i++)
ss[i*2+2]=s[i];
len=n*2+1;ss[0]='\$';
int max=0,id=0;
for(int i=1;i<=len;i++)
{
if(max>i)
pp[i]=Math.min(pp[id*2-i],max-i);
else pp[i]=1;
while(ss[i+pp[i]]==ss[i-pp[i]])
pp[i]++;
if(i+pp[i]>max) { max=i+pp[i];id=i;}
}
}
static void insert(int a,int b,int l,int r)
{
int u=a,v=b,p;
for(int i=l;i<=r;i++)
{
p=ss[i]-'a';
for(int k=0;k<5;k++)
ch[u][k]=ch[v][k];
cnt[u]=cnt[v]+1;
ch[u][p]=++sz;
u=ch[u][p];v=ch[v][p];
}
cnt[u]=cnt[v]+1;
}
static int query(int a,int b,int k)
{
int u=a,v=b,p;
for(int i=0;i<tt[k].length;i++)
{
p=tt[k][i]-'a';
u=ch[u][p];v=ch[v][p];
}
return cnt[v]-cnt[u];
}

public static void main(String[] args) throws IOException {
//Scanner in=new Scanner(System.in);
while(in.nextToken()!=StreamTokenizer.TT_EOF)
{
s=in.sval.toCharArray();
n=s.length;
Manacher();
for(int i=n;i>0;i--) ss[i]=s[i-1];
m=nextInt();
for(int i=1;i<=m;i++)
{
aa[i]=nextInt();bb[i]=nextInt();
tt[i]=next().toCharArray();
cc[i]=tt[i].length;
}
for(int i=1;i<=m;i++) ans[i]=0;
for(int k=1;k<=10;k++)
{
sz=0;rt[0]=++sz;
for(int i=1;i<=n;i++)
{
a=pp[i*2]/2;
if(a>=k)
{
rt[i]=++sz;
insert(rt[i],rt[i-1],i,i+k-1);
}
else rt[i]=rt[i-1];
}
for(int i=1;i<=m;i++)
{
if(cc[i]>k||k*2-1>bb[i]-aa[i]+1) continue;
ans[i]+=query(rt[aa[i]+k-2],rt[bb[i]-k+1],i);
}
sz=0;rt[0]=++sz;
for(int i=1;i<=n;i++)
{
a=pp[i*2-1]/2;
if(a>=k)
{
rt[i]=++sz;
insert(rt[i],rt[i-1],i,i+k-1);
}
else rt[i]=rt[i-1];
}
for(int i=1;i<=m;i++)
{
if(cc[i]>k||k*2>bb[i]-aa[i]+1) continue;
ans[i]+=query(rt[aa[i]+k-1],rt[bb[i]-k+1],i);
}
}
for(int i=1;i<=m;i++)
out.println(ans[i]);
}
out.flush();
}
}
``````
原文作者：Trie树
原文地址: https://blog.csdn.net/ac_machine/article/details/52131499
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。