HDU 5157 Harry and magic string

Problem Description

T:x=T[a1…b1],y=T[a2…b2](where a1 is the beginning index of 

x,b1 is the ending index of x. 

a2,b2 as the same of y), if both x and y are palindromes and 

b1<a2 or b2<a1

Input

There are several cases.

For each test case, there is a string T in the first line, which is composed by lowercase characters. The length of T is in the range of [1,100000].

Output

For each test case, output one number in a line, indecates the answer.

Sample Input

aca
aaaa      

Sample Output

Hint

For the first test case there are 4 palindrome substrings of T.

They are:
S1=T[0,0]
S2=T[0,2]
S3=T[1,1]
S4=T[2,2]
And there are 3 disjoint palindrome substring pairs.
They are:
(S1,S3) (S1,S4) (S3,S4).
So the answer is 3.      

#pragma comment(linker, "/STACK:102400000,102400000")
#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 maxn = 1e5 + 10;
LL a[maxn];
char s[maxn];

struct linklist
{
  int nt[maxn], ft[maxn], u[maxn], v[maxn], sz;
  void clear() { sz = 0; }
  void clear(int x) { ft[x] = -1; }
  int get(int x, int y)
  {
    for (int i = ft[x]; i != -1; i = nt[i])
    {
      if (u[i] == y) return v[i];
    }
    return 0;
  }
  void insert(int x, int y, int z)
  {
    u[sz] = y;  v[sz] = z;
    nt[sz] = ft[x]; ft[x] = sz++;
  }
};

struct PalindromicTree
{
  const static int maxn = 1e5 + 10;
  const static int size = 26;
  linklist next;
  int sz, tot, last;
  int fail[maxn], len[maxn], cnt[maxn];
  char s[maxn];
  void clear()
  {
    len[1] = -1; len[2] = 0;
    fail[1] = fail[2] = 1;
    cnt[1] = cnt[2] = tot = 0;
    last = (sz = 3) - 1;
    next.clear();   next.clear(1);  next.clear(2);
  }
  int Node(int length)
  {
    len[sz] = length;
      cnt[sz] = 1; next.clear(sz);
    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 (!(last = next.get(y, x)))
    {
      next.insert(y, x, last = Node(len[y] + 2));
      fail[last] = len[last] == 1 ? 2 : next.get(getfail(fail[y]), x);
      cnt[last] += cnt[fail[last]];
    }
    return cnt[last];
  }
}solve;

int main()
{
  while (scanf("%s", s) != EOF)
  {
    LL ans = a[0] = 0, len = strlen(s);
    solve.clear();
    for (int i = 1; i <= len; i++)
    {
      a[i] = a[i - 1] + solve.add(s[i - 1]);
    }
    solve.clear();
    for (int i = len; i; i--)
    {
      ans += solve.add(s[i - 1])*a[i - 1];
    }
    printf("%lld\n", ans);
  }
  return 0;
}