2017/04/26 Emmm……dull..


Giving a string consists of ‘0’ ~ ‘9’, for all the cyclical string of the given string determine how many of them are greater/less than or equal to the original string.

Let S denote the original string, we construct string T by putting S back to itself.
Let’s use extend-KMP to calculate the LCP of S and all the suffixes of T, as we know, each of which contains one of the cyclical string of S as prefix.
To compare two strings, we only need to compare the character just after the LCP of the two strings.

Note that if S’s minimal period is d and d|length(S), all the cyclical string of S must appear length(S)/d times.


Giving a string S, calculate \sum i*k for all tuples (i, j, k) satisfying 1 \leq i\leq j \textless k \leq length(S), S[i\cdots j] and S[j + 1\cdots k] are both palindrome strings.

Practising palindrome tree.
Calculate the number and total lengths of palindrome strings ending by i.
Reverse the original string and do the same thing.