Programmer Vasya was down on his luck. Instead of a vacation, he was
sent to a scientific conference.
“It is necessary to increase your competence,” his boss said,
“it’s an important conference on cryptography, and it’s held in France, where
they used encryption in the days of de Richelieu and cracked codes in the days
One of the talks at the conference was about the attempts to solve Bacon’s
ciphers. The speaker proposed a hypothesis that the key to Bacon’s secrets
could be found if all possible substrings of Bacon’s works were analyzed.
“But there are too many of them!” Vasya expressed his astonishment.
“Not as many as you think,” the speaker answered, “count them all and you’ll see it
That evening Vasya found on the Web the complete set of Bacon’s works. He wrote
a program that converted the texts into one long string by removing all
linebreaks, spaces, and punctuation marks. And now Vasya is confused because he
doesn’t know how to calculate the number of different substrings of this
You are given a nonempty string consisting of lowercase English letters.
The string is no longer than 5000 symbols.
Output the number of different substrings of this string.
Problem Author: Alex Gevak
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007