题意：

Problem C. String Magic (Easy Version)

Given a string S of length n (indexed from 1 to n) , define f(S) equal to the number of pair (i; j) that:

• 1 <= i < j <= n

• j - i + 1 = 2k; k > 0 (j - i + 1 is even)

• S[i; i + k - 1] = S[i + k; j]

• S[i; i + k - 1] is a palindrome

Here S[L,R] denotes the substring of S with index from L to R.

A palindrome is a string that reads the same from left to right as from right to left.

We need  to calculate f(S).

题解：

主席树 + 回文串

in:

3

aaaa

abaaba

ababa

out:

4

2

0