Problems
SETI
SETI
Amateur astronomers Tom and Bob try to find radio broadcasts of extraterrestrial civilizations in the air. Recently they received some strange signal and represented it as a word consisting of small letters of the English alphabet. Now they wish to decode the signal. But they do not know what to start with.
They think that the extraterrestrial message consists of words, but they cannot identify them. Tom and Bob call a subword of the message a \textit{potential word} if it has at least two non-overlapping occurrences in the message.
For example, if the message is "\textbf{abacabacaba}", "\textbf{abac}" is a potential word, but "\textbf{acaba}" is not because two of its occurrences overlap.
Given a message \textbf{m} help Tom and Bob to find the number of potential words in it.
\InputFile
Input file contains one string that consists of small letters of the English alphabet. The length of the message doesn’t exceed \textbf{10000}.
\OutputFile
Output one integer number --- the number of potential words in a message.
Input example #1
abacabacaba
Output example #1
15