4
$\begingroup$

Let's say I have the following string:

XXXXXAYYYYBYYYYCXXXXXDYYYY

We can see that the substring XXXXX is 5 characters long, and repeated 2 times. So it covers 10 characters. This is the longest repeated substring

However, there's the substring YYYY which is 4 characters long, and repeated 3 times and therefore covers 12 characters.

I want to find the repeated substring of length of at least 2 with the highest coverage, and that don't overlap.

Is there an efficient algorithm that does so?

This is the current algorithm I'm using (written in Java), which is naive and slow :

String highestCoveringRepeatedSubstring(String string) {
  int highestCoverage = 0;
  String highestCoveringRepeatedSubstring = "";
  for (int length = 1; length < string.length(); length++) {
    for (int index = 0; index < string.length() - length; index++) {
      String substring = string.substring(index, index + length);
      int count = 0;
      for (int i = index; i >= 0; i = string.indexOf(substring, i + length)) {
        count++;
      }
      if (count > 1 && length * count >= highestCoverage) {
        highestCoverage = length * count;
        highestCoveringRepeatedSubstring = substring;
      }
    }
  }
  return highestCoveringRepeatedSubstring;
}
$\endgroup$
  • $\begingroup$ Your code will under-count substrings that partially overlap themselves -- e.g. XX will be assigned a coverage of 2 for the string XXX, when it really covers all 3 characters. $\endgroup$ – j_random_hacker Feb 12 at 15:28
  • $\begingroup$ @j_random_hacker Indeed, I forgot to add that the string shouldn't overlap. So I added that in the question. Thank you! The code shown returns the expected result. $\endgroup$ – Olivier Grégoire Feb 12 at 15:34
  • $\begingroup$ You're welcome. It's a slight shame though, since if overlapping substrings were allowed, it would suffice to test only substrings corresponding to internal nodes of a suffix tree -- and there are only $O(n)$ of these, vs. $O(n^2)$ substrings overall. That said, even using just these internal-node substrings, I didn't yet see a way to make the overall time complexity subquadratic. (Your current time complexity seems to be $O(n^3)$.) $\endgroup$ – j_random_hacker Feb 12 at 16:04
  • 1
    $\begingroup$ Can you convert your Java code to pseudocode? Not everyone knows Java. $\endgroup$ – Yuval Filmus Feb 12 at 16:46

Your Answer

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

Browse other questions tagged or ask your own question.