0
$\begingroup$

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.

$\endgroup$
  • 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 at 14:33
  • $\begingroup$ build suffix array $\endgroup$ – Bulat Mar 22 at 16:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Apass.Jack Mar 23 at 2:10
  • $\begingroup$ I think you might want to check out the Main-Lorentz algorithm for finding repetitions $\endgroup$ – BearAqua Mar 24 at 18:31
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.