CodeChef PALPROB Palindromeness

All submissions for this problem are available.

Read problems statements in ​​Mandarin Chinese ​​​and ​​Russian​​.

Let us define the palindromeness of a string in the following way:

• If the string is not a palindrome, its' palindromeness is zero.
• The palindromeness of an one-letter string is 1.
• The palindromness of a string S of the length greater than one is 1 + "palindromeness of the string that is formed by the first [|S|/2] symbols of S".

Let us consider some examples for better understanding:

• The palindromeness of the string zxqfd is 0, since the string is not a palindrome.
• The palindromeness of the string a is 1, by definition.
• The palindromeness of the string aa is 2, beucase for "aa" we get 1 + palindromeness of "a", that is one, so we get 2.
• The palindromeness of the string abacaba is 3.

S. Find the sum of the palindromenesses of all the non empty substrings of S (i.e.S[i..j], where i <= j). In other words, you have to calculate the sum of palindromenesses of N * (N + 1) / 2substrings of S, where N is the length of S.

Input

T denoting the number of test cases. The description of T

S

Output

For each test case, output a single line containing an integer corresponding to the answer to the problem.

Constraints

• 1 ≤ T ≤ 3
• S

Subtask 1 (15 points):

• 1 ≤ |S| ≤ 100

Subtask 2 (23 points):

• 1 ≤ |S| ≤ 1000

Subtask 3 (62 points):

• 1 ≤ |S| ≤ 105

Example

Input:
2
zxqfd
aba

Output:
5
5      

Explanation

Example case 1: There is no palindrome that occurs as the substring of zxqfd and has the length more than 1. The individual characters are palindromes of the palindromeness of 1.

Example case 2: The palindromeness of aba is 2 and the sum of the palindromenesses of single characters is 3.

此题和​​Gym 100543G​​有异曲同工之妙，同样是需要一个half指针来计算分数，最后统计一下即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 777777777;
const int maxn = 1e5 + 10;
int T;
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], half[maxn], len[maxn], sc[maxn];
  LL cnt[maxn];
  char s[maxn];
  int Node(int length)
  {
    memset(next[sz], 0, sizeof(next[sz]));
    len[sz] = length;  cnt[sz] = 0; return sz++;
  }
  void clear()
  {
    fail[2] = fail[1] = 1;
    half[2] = half[1] = 1;
    sz = last = 1;
    sc[1] = sc[2] = tot = 0;
    Node(-1); Node(0);
  }
  int getfail(int x)
  {
    while (s[tot] != s[tot - len[x] - 1]) x = fail[x];
    return x;
  }
  void add(char pos)
  {
    int x = (s[++tot] = pos) - 'a', y = getfail(last);
    if (!(last = next[y][x]))
    {
      last = next[y][x] = Node(len[y] + 2);
      fail[last] = len[last] == 1 ? 2 : next[getfail(fail[y])][x];
      if (len[last] == 1) half[last] = 2;
      else
      {
        int z = half[y];
        while (s[tot] != s[tot - len[z] - 1] || len[z] + len[z] + 4 > len[last]) z = fail[z];
        half[last] = next[z][x];
      }
      sc[last] = 1 + (len[last] / 2 == len[half[last]] ? sc[half[last]] : 0);
    }
    ++cnt[last];
  }
  void work()
  {
    LL ans = 0;
    for (int i = sz - 1; i > 2; i--)
    {
      cnt[fail[i]] += cnt[i];
      ans += cnt[i] * sc[i];
    }
    cout << ans << endl;
  }
}solve;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%s", s);
    solve.clear();
    for (int i = 0; s[i]; i++) solve.add(s[i]);
    solve.work();
  }
  return 0;
}