题意：给你一个字符串，给你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 = 1000+10; const int sigma=26; const ll mod = 1000000007; const int INF = 0x3f3f3f; const db eps = 1e-9; 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]=0; len[p]=l; return p++; } inline void init() { n=0, p=0, last=0; memset(next, 0, sizeof(next)); memset(cnt, 0, sizeof(cnt)); memset(len, 0, sizeof(len)); memset(fail, 0, sizeof(fail)); newnode(0), newnode(-1); s[n]=-1; fail[0]=1; //cout<<n<<" "<<p<<" "<<last<<endl; } inline int FL(int x) { while(s[n-len[x]-1]!=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]+2); fail[now]=next[FL(fail[cur])][c]; next[cur][c]=now; } last=next[cur][c]; ++cnt[last]; } inline ll countt() { ll pk=0; for (int i=p-1; ~i; --i) { cnt[fail[i]]+=cnt[i]; pk++; } return pk; } }p; char s[maxn]; int ans[maxn][maxn]; void solve(){ memset(ans, 0, sizeof(ans)); scanf("%s",s); int len=strlen(s); for (int i=0; i<len; i++) { p.init(); for (int j=i; j<len; j++) { p.add(s[j]); ans[i][j] = p.p-2; } } int q; scanf("%d", &q); while(q--) { int a, b; scanf("%d%d", &a, &b); printf("%d ", ans[a-1][b-1]); } } int main() { int t = 1; // freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%d", &t); while(t--) solve(); return 0; }