Algorithm that finds all the recurring substrings in a string

Question

I need to find all the recurring substrings in a string without considering the "overlapping" recurring substrings. For example if I have ABCDABCDACCACCACCABDC, here the recurring substrings are ABCD (2 times), ACC (3 times) and AB (3 times) etc... but without considering the cases like CCACC that would repeat two times if you take the common CC (the CC in bold ABCDABCDACCACCACCABDC). Is there an algorithm that can find these substrings and that has been implemented in some programming language like Python ?

In Google you can find many ways to obtain the "longest common substring". But I need all the recurring substrings, so not only the longest one but of all the lengths... (like the example that I wrote).

I suspect that it is not a trivial problem and my actual poor knowledges in programming do not help me in solving the problem. So I ask you if some matematician has invented it . Maybe there is an algorithm to find this that has a precise name.

Thank you in advance.

Answer 1

A simple algorithm for this problem would be:

given a string s of length N
for i between 0 and N / 2
    for j between 2 and N / 2
        for k between j and N - i - j:
            if s[i : i+j] == s[i + k : i + j + k]
                count an occurence of this substring (s[i:i+j])

Where $s[x:y]$ is the substring from index $x$ to $y$.

$i$ is the start of the string, $j$ is the length of a substring, and $k$ is used to find reoccurences of the string (starting at $i+k$).

This has a runtime complexity of $O(n^3)$ where $n$ is the length of the string s. It can certainly be optimized by preprocessing the string and applying dynamic programming principles, but you haven't specified any requirements on performance.

However - Your question is likely better placed on stackoverflow.