Finding often repeating substrings in multiple strings

Question

I'm currently looking for an algorithm to find often repeating substrings in one or multiple strings. However, my search until now was not really successful. I try to illustrate the problem on the following example strings:

S1: ABCCCDxxxxxxABCCCDxxxxABCCCD
S2: xxxxxABCCCDxxxxABCCCDxxxxxxx
...
S10: xxABCCCDxxxxxxxxABCCCDxxxxxx

In the given example strings S1, S2 up to S10, the substring ABCCCD occurs multiple times, making it an often repeating substring, and thus interesting for me. However, when trying to find an algorithm that helps with finding such substrings, I often end up at the longest common substring problem, which would help me find the longest common substring between S1 and S2, however, it would ignore the repetition of the substring.

Does an algorithm exist, that can help me with this problem? Additionally, it would be quite interesting to set additional constraints, such "substring must occur at least n times" or "substring must be at least n characters" long.

Answer 1

Let's say you are looking for substrings that occur at least $c$ times in each string and have length at least $k$. Furthermore, lets say we're looking for maximally repeated substrings i.e. if $R$ is our solution set of substrings, there exists no pair $r_i, r_j\in R$ such that $r_i$ is a substring of $r_j$.

Offline option

Construct a generalized suffix tree from all input strings. Any node at depth at least $k$ that has at least $c$ leaves from each input string (i.e. at least $c$ $\$_1$ leaves, at least $c$ $\$_2$ leaves and so on) is $blue$ and each $blue$ node with no $blue$ children is also $red$. The set of substrings represented by $red$ nodes is the set of maximally repeated substrings. This runs in time $O(mn)$ where you have $n$ input strings of length at most $m$.

Answer 2

Why not use a sliding window type of algorithm? Let's say you are looking for the most common substring(s) of size exactly $k$. Slide a window of size $k$ on each of your strings and use a dictionary to count how many times each substring of size $k$ appears. At the end, iterate over the dictionary and pick the substring with the highest count.