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?