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:

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.

  • 2
    $\begingroup$ 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? $\endgroup$
    – Discrete lizard
    Mar 22, 2019 at 14:33
  • $\begingroup$ build suffix array $\endgroup$
    – Bulat
    Mar 22, 2019 at 16:29
  • $\begingroup$ I think you might want to check out the Main-Lorentz algorithm for finding repetitions $\endgroup$ Mar 24, 2019 at 18:31

2 Answers 2


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$.


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.

  • $\begingroup$ This needs some sort of hashing to not have a time complexity quadratic in $k$ $\endgroup$ Mar 7, 2020 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.