8
\$\begingroup\$

Here's my code that takes a large string, and searches for the longest reoccurring substring. It compares the first letter with every other until it finds a match, then saves it. Then it compares the first 2 letters with every other until it finds a match then saves it. Then 3, 4, etc... Then it comes back around and starts with the second letter and checks the first letter, then the first 2, then the first 3, etc.

I plan on using this on text files as large as a novel. The time complexity is horrendous. I think it's O(n# of characters in the text file). Is there any other way to approach this?

def largest_substring(string):

    length = 0
    x=0
    y=0

    for y in range(len(string)):       
        for x in range(len(string)):     
            substring = string[y:x]                   
            if len(list(re.finditer(re.escape(substring),string))) > 1  and len(substring) > length:
                match = substring
                length = len(substring)
    return match
\$\endgroup\$
  • \$\begingroup\$ I'm sure there's a clever algorithm, but my first thought is start big and get smaller, that way the first duplicate phrase you find its the largest and then you're done. There's no point in finding all the less than largest duplicates first I would think. Also since you're only checking for membership of a substring you can use the in keyword instead of regex, which are expensive. However you might could accomplish this entire task with a single clever regex using backreferences and forward lookahead... force it to find the longest string which is followed by itself at some point. \$\endgroup\$ – flutefreak7 Sep 19 '14 at 6:38
  • 1
    \$\begingroup\$ Take a look at the "longest repeated substring problem" article on Wikipedia — you'll see there's a linear algorithm using suffix trees. \$\endgroup\$ – Gareth Rees Sep 19 '14 at 13:45
3
\$\begingroup\$

Thanks for this interesting problem. My approach is to convert the string into two lists (actually one list and one deque). For every iteration, shift one of the lists by one item and compare the two lists to find the maximum match.

What I managed to achieve has a complexity of \$O(n*n)\$:

def largest_substring_algo1(string):
    l = list(string)
    d = deque(string[1:])
    match = []
    longest_match = []
    while d:
        for i, item in enumerate(d):
            if l[i]==item:
                match.append(item)
            else:
                if len(longest_match) < len(match):
                    longest_match = match
                match = []
        d.popleft()
    return ''.join(longest_match)
\$\endgroup\$
  • \$\begingroup\$ This is effectively performing an auto-correlation (except that the usual scalar-product function is now a equals-length function). \$\endgroup\$ – Toby Speight Nov 7 '17 at 15:43
2
\$\begingroup\$

I guess a prefix tree might help.

  • Build a parallel array of pointers (sorry for a C-speak) into an original text.
  • Sort it.
  • Scan it for a longest match in two consecutive entries.

Overall complexity is \$O(ns)\$

Where \$n\$ is the length of the text and \$s\$ is the length of the longest recurring substring.

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