链接:
https://ac.nowcoder.com/acm/contest/57362/I
来源:牛客网
Luluu is a “Square” magician from Eorzea. “Square” magicians are experts to use “Square” spells.
Every spell can be represented as a non-empty string containing only lower-case English characters. The “Square” spells are those of even length which the first half is identical to the second half. For example,
abcabc and
aaaa are “Square” spells, while
aaa and
abcabd are not.
Today, Luluu found a powerful “Square” spell from Grimoire, but unfortunately, the book page is damaged, so some parts of the spell are not readable anymore.
More specifically, the original “Square” spell is of the format
p+s+q+tp + s + q + tp+s+q+t, where
sss and
ttt are two constant strings, but
ppp and
qqq are the two unreadable parts of the spell. From some investigation, Luluu believes
ppp and
qqq should be of the same length that doesn't exceeds
mmm.
Now, Luluu asks your help to calculate the number of all possible original “Square” spells. Could you help this poor magician?