# finding all cyclic substrings of a string

I have been stuck on this problem for a while now; any help would be appreciated.

Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For example, "abbccbbadad" has 3 because "bb" is composed of 2 "b"s, "cc" is composed of 3 "c"s, and "adad" is composed of 2 "ad"s.

My solution uses hashing and currently runs in n^2 time, which is fine because the length of the string is <= 5000. However, my program uses n^3 space. I am confident that a solution requiring n^2 space and n^2 time will pass. Is there a more efficient solution?

• What do you mean by consecutive string? Do you mean a (nontrivial) power? – Yuval Filmus Mar 28 '20 at 21:20
• a substring which is just 2 or more repeats of a string, like "abcabcabc" is 3 "abc"s which are consecutive. – pblpbl Mar 28 '20 at 21:22
• The English term is power. – Yuval Filmus Mar 28 '20 at 21:23

Any algorithm that runs in $$O(n^2)$$ time can access at most $$O(n^2)$$ different memory locations during the course of its execution. Thus, if you replace memory with a hashtable (instead of accessing address $$a$$, access the hashtable at key $$a$$), you obtain an algorithm with expected running time $$O(n^2)$$ and space $$O(n^2)$$. If you care about theoretical proofs, you can use a balanced binary search tree instead of a hashtable and obtain a worst-case time bound of $$O(n^2 \log n)$$ time and $$O(n^2)$$ space.