题意:给你一个字符串,给你Q次询问,每一次问你从l-r里有多少个回文串。
思路:len很小,所以直接遍历区间求就好了。
/* gyt
Live up to every day */
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = +;
const int sigma=;
const ll mod = ;
const int INF = 0x3f3f3f;
const db eps = 1e-;
struct ptree{
char s[maxn];
int next[maxn][sigma], fail[maxn], cnt[maxn], len[maxn];
int last, n, p;
ll res;
inline int newnode(int l) {
cnt[p]=;
len[p]=l;
return p++;
}
inline void init() {
n=, p=, last=;
memset(next, , sizeof(next));
memset(cnt, , sizeof(cnt));
memset(len, , sizeof(len));
memset(fail, , sizeof(fail));
newnode(), newnode(-);
s[n]=-;
fail[]=;
//cout<<n<<" "<<p<<" "<<last<<endl;
}
inline int FL(int x) {
while(s[n-len[x]-]!=s[n]) x=fail[x];
return x;
}
void add(char c) {
c-='a';
s[++n]=c;
int cur=FL(last);
if (!next[cur][c]) {
int now=newnode(len[cur]+);
fail[now]=next[FL(fail[cur])][c];
next[cur][c]=now;
}
last=next[cur][c];
++cnt[last];
}
inline ll countt() {
ll pk=;
for (int i=p-; ~i; --i) {
cnt[fail[i]]+=cnt[i];
pk++;
}
return pk;
}
}p;
char s[maxn];
int ans[maxn][maxn];
void solve(){
memset(ans, , sizeof(ans));
scanf("%s",s);
int len=strlen(s);
for (int i=; i<len; i++) {
p.init();
for (int j=i; j<len; j++) {
p.add(s[j]);
ans[i][j] = p.p-;
}
}
int q; scanf("%d", &q);
while(q--) {
int a, b; scanf("%d%d", &a, &b);
printf("%d\n", ans[a-][b-]);
}
}
int main() {
int t = ;
// freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &t);
while(t--)
solve();
return ;
}