Distinct Repeating Strings
Given a text t, you are asked to find out the number of unique non-empty repeating strings present in t. Repeating strings can be formed by concatenating the same string s to itself → s + s.
Input
The first line of the input contains the text t (1 ≤ |t| ≤ 1000).
Output
The program should print the number of repeating strings present in t.
Examples
Input | Output |
|---|---|
yeeey | 1 |
abcabcabc | 3 |
Explanation
yeeey → ee
abcabcabc → abcabc, bcabca, cabcab
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB