Repeated Substrings#7530
String analysis often arises in applications from biology and chemistry, such as the study of DNA and protein molecules. One interesting problem is to find how many substrings are repeated (at least twice) in a long string.
In this problem, you will write a program to find the total number of repeated substrings in a string of at most alphabetic characters. Any unique substring that occurs more than once is counted. As an example, if the string is "aabaab", there are repeated substrings: "a", "aa", "aab", "ab", "b". If the string is "aaaaa", the repeated substrings are "a", "aa", "aaa", "aaaa". Note that repeated occurrences of a substring may overlap (e.g. "aaaa" in the second case).
Consists of at most cases. The first line contains a positive integer, specifying the number of cases to follow. Each of the following line contains a nonempty string of up to alphabetic characters.
For each test print one line containing the number of unique substrings that are repeated. You may assume that the correct answer fits in a signed -bit integer.
Example 1