Find longest repetitive sequence in a string

by

This problem is a variant of the longest repeated substring problem and there is an O(n)-time algorithm for solving it that uses suffix trees. The idea (as suggested by Wikipedia) is to construct a suffix tree (time O(n)), annotate all the nodes in the tree with the number of descendants (time O(n) using a DFS), and then to find the deepest node in the tree with at least three descendants (time O(n) using a DFS). This overall algorithm takes time O(n).

That said, suffix trees are notoriously hard to construct, so you would probably want to find a Python library that implements suffix trees for you before attempting this implementation. A quick Google search turns up this library, though I’m not sure whether this is a good implementation.

Another option would be to use suffix arrays in conjunction with LCP arrays. You can iterate over pairs of adjacent elements in the LCP array, taking the minimum of each pair, and store the largest number you find this way. That will correspond to the length of the longest string that repeats at least three times, and from there you can then read off the string itself.

There are several simple algorithms for building suffix arrays (the Manber-Myers algorithm runs in time O(n log n) and isn’t too hard to code up), and Kasai’s algorithm builds LCP arrays in time O(n) and is fairly straightforward to code up.

Hope this helps!

More Related Contents:

  1. How t extract last part of a text in python [duplicate]
  2. How to understand regular expression with python?
  3. Speed up millions of regex replacements in Python 3
  4. Is there a simple way to remove multiple spaces in a string?
  5. How to correctly sort a string with a number inside? [duplicate]
  6. Split string on whitespace in Python [duplicate]
  7. Fast punctuation removal with pandas
  8. Remove all special characters, punctuation and spaces from string
  9. Split a string at uppercase letters
  10. Python regex match OR operator
  11. Python string ‘in’ operator implementation algorithm and time complexity
  12. How to match any string from a list of strings in regular expressions in python?
  13. How to extract an IP address from an HTML string?
  14. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  15. Regex for existence of some words whose order doesn’t matter
  16. Splitting a string with repeated characters into a list
  17. How to test if one string is a subsequence of another? [duplicate]
  18. How would I get everything before a : in a string Python
  19. Python regex: splitting on pattern match that is an empty string
  20. Mass string replace in python?
  21. Remove duplicate chars using regex?
  22. Python: find closest string (from a list) to another string
  23. How to remove symbols from a string with Python? [duplicate]
  24. How can I split this comma-delimited string in Python? [duplicate]
  25. String similarity metrics in Python [duplicate]
  26. Remove Sub String by using Python
  27. How can I interleave or create unique permutations of two strings (without recursion)
  28. How do I verify that a string only contains letters, numbers, underscores and dashes? [duplicate]
  29. How to use str.contains() with multiple expressions in pandas dataframes
  30. Splitting a math expression string into tokens in Python

Leave a Comment