HDU 5658 CA Loves Palindromic

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

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

Q

Sample Input

1
abba
2
1 2
1 3      

Sample Output

Hint

In first query, the palindromic substrings in the substring $S[1,2]$ are "a","b".

In second query, the palindromic substrings in the substring $S[1,2]$ are "a","b","bb".

Note that the substring "b" appears twice, but only be counted once.

You may need an input-output optimization.

给定一个字符串，求给定区间的本质不同的回文子串，直接利用回文树即可。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
int T, n, ans[maxn][maxn], l, r;
char s[maxn];

struct PalindromicTree
{
  const static int maxn = 1e5 + 10;
  const static int size = 26;
  int next[maxn][size], last, sz, tot;
  int fail[maxn], len[maxn], cnt[maxn];
  char s[maxn];
  void clear() 
  { 
    len[1] = -1; len[2] = 0;
    fail[2] = fail[1] = 1;  
    last = (sz = 3) - 1;  
    cnt[1] = cnt[2] = tot = 0;
    memset(next[1], 0, sizeof(next[1]));
    memset(next[2], 0, sizeof(next[2]));
  }
  int Node(int length)
  {
    memset(next[sz], 0, sizeof(next[sz]));
    len[sz] = length;   return sz;
  }
  int getfail(int x)
  {
    while (s[tot] != s[tot - len[x] - 1]) x = fail[x];
    return x;
  }
  int add(char pos)
  {
    int x = (s[++tot] = pos) - 'a', y = getfail(last);
    if (next[y][x]) { last = next[y][x]; return 0; }

    last = next[y][x] = Node(len[y] + 2);
    fail[sz] = len[sz] == 1 ? 2 : next[getfail(fail[y])][x];
    return sz++, 1;
  }
}solve;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%s", s);
    for (int i = 0; s[i]; i++)
    {
      solve.clear();
      ans[i + 1][i] = 0;
      for (int j = i; s[j]; j++)
      {
        ans[i + 1][j + 1] = ans[i + 1][j] + solve.add(s[j]);
      }
    }
    scanf("%d", &n);
    while (n--)
    {
      scanf("%d%d", &l, &r);
      printf("%d\n", ans[l][r]);
    }
  }
  return 0;
}