# Finding often repeating substrings in multiple strings

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.

• In general, the longest common subsequence problem for multiple sequences is NP-hard. However, looking for "long enough" "common enough" subsequences might be feasible. Could you try to formalise your problem by offering suggestions as how to determine when a subsequence is common enough and when it is long enough? Does it matter if a sequences occurs a lot but only in a few different sequences? Does it matter at all in which sequence a subsequence occurs? – Discrete lizard Mar 22 '19 at 14:33
• build suffix array – Bulat Mar 22 '19 at 16:29
• @Discretelizard I just edit the question to clarify its intention. You might want to delete your comment or replace it with a new one as well as delete this comment of mine. – John L. Mar 23 '19 at 2:10
• I think you might want to check out the Main-Lorentz algorithm for finding repetitions – BearAqua Mar 24 '19 at 18:31

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$$.
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$$.
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.
• This needs some sort of hashing to not have a time complexity quadratic in $k$ – Antti Röyskö Mar 7 '20 at 8:33