[SPOJ] VPALIN

Let $P=A^m=\underset{m \: times}{\underbrace{AA..A}}$
It's easy to prove that: if P is a palindrome then A is also a palindrome

Let Base(P) = the shortest string A such that $P=A^m$
Let P, Q be two palindromes. We can prove that:
PQ is a palindrome iff Base(P) = Base(Q)

Therefore, the problem is reduced to finding the period of a string, which can be done in O(n) using KMP's Next table.

To efficiently count the number of appearances of a base, we can use a hash function from a string into int64 range.

int64 hash(char *s, int n) {
 int64 h=0;
 FOR(i,n) h=31*h+s[i];
 return h;
}