Telling the length of the highest common substring between 2 words

Question

This takes two strings and returns the length of the largest common substring.

Example:

contando_sstring_igual("abcdef", "cdofhij")
# 2

Because the longest common substring = "cd", so it returns the length of it (2).

Here is the code:

def contando_sstring_igual(string1, string2):
    resposta = ""
    tamanho1 = len(string1)
    tamanho2 = len(string2)
    for i in range(tamanho1):
        for j in range(tamanho2):
            lcs_temp = 0
            igual = ''
            while i + lcs_temp < tamanho1 and j + lcs_temp < tamanho2 and string1[i + lcs_temp] == string2[j + lcs_temp]:
                igual += string2[j+lcs_temp]
                lcs_temp += 1
            if len(igual) > len(resposta):
                resposta = igual
    return len(resposta)


while True:
    a = input()
    b = input()
    if a is None or b is None:
        break
    else:
        print(contando_sstring_igual(a, b))

I need to make my code work significantly faster. It does the job right, but not fast enough. I need to avoid the timeout error I'm getting on the exercise and I'm not even close to figuring out how to do it, without the loop.

Answer 1

You should use English for everyone's benefit unless you're certain your code will be read only by speakers of a specific language.

I will refrain from addressing algorithms with better complexity, if any, and I will focus on how you can improve your current method, which has 3 inefficiencies.

1. You should only loop for the substring you're testing from 0 up to the length of the smaller string.
2. Instead of searching for the existence of the substring in the other string using a Python level loop, which is slow, take advantage of substring in string which does everything in C-loops under the hood. To fully take advantage of the C-loop speedup, you want string to be the longer of the two strings.
3. If you don't find a substring of length 3, it's obvious there will no substrings of length 4 or longer, either. You should check for the existence of at least one substring of length n before moving on to search for length n + 1. As soon as you find no substring for some length, n, you can prematurely end your search right there.

With the above improvements in mind, your code could look like this

def longest_common_substring_length(s1, s2):
    # the longest substring length can't be longer than the smaller string
    substr_len = min(map(len, (s1, s2)))
    # ensure `s2` is the longer string so that `s1[...] in s2` takes advantage
    # of the substring existence test speedup from C-level loops.
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    longest = 0
    for length in range(1, substr_len+1):
        found_substring = False
        for index in range(0, len(s1)-length+1):
            if s1[index:index+length] in s2:
                found_substring = True
                longest = length
                break
        if not found_substring:
            break
    return longest

---

Other comments

• lcs_temp is not a descriptive name. Also, you're now mixing Portuguese with English abbreviations, which could be very confusing!
• You don't need to build strings with igual and resposta, since you never return the substring itself. You can just use the same logic, but instead keep tracking of the longest substring length using lcs_temp.
• Your main program's exit condition will never be reached because input() in Python 3 always returns a string and as such a is None will always be false. If you intend to use an empty string for the exit condition, you can simply check for if not a.
• Additionally, since that conditional block will be executed only if the condition if met, the else block isn't necessary. Just indent print(...) back to the while level.

---

Previous answer

I had previously suggested to start the search from the longest substring possible and reverse the search down to 0. This method will suffer if both strings are fairly long and aren't likely to share a long substring. Imagine two random strings of length 50. They aren't likely to have a common substring longer than 1-3 characters, but the reverse search will first check for 50, then 49, etc.

def longest_common_substring_length(s1, s2):
    # the longest substring length can't be longer than the smaller string
    substr_len = min(map(len, (s1, s2)))
    # ensure `s2` is the longer string so that `s1[...] in s2` takes advantage
    # of the substring existence test speedup from C-level loops.
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    for length in range(substr_len, 0, -1):
        for index in range(0, len(s1)-length+1):
            if s1[index:index+length] in s2:
                return length
    return 0

Answer 2

English please!

Identifiers and comments reallly really should be in English for all code you write. Otherwise it will be hard to impossible to take part in the completely globalized IT world we're living in.

Break long lines

Your lines shouldn't be longer than 79 characters. Break them before binary operators:

while i + lcs_temp < tamanho1 \
      and j + lcs_temp < tamanho2 \
      and string1[i + lcs_temp] == string2[j + lcs_temp]:

---

performance related comments still under construction ;)

Ok, I got a bit hooked up here, and I think I've got something usable out of it. I'm though not yet posting the code as it's late here and currently really a mess, so I'll tidy up tomorrow and post it then.

Teaser (ignore the x-axis label):

Code for measurement, though killed after size 100 due to long runtime:

for size in chain(range(10, 100, 10), range(100, 1000, 100)):
    times = map(lambda v: timeit('lcsl_{}("abcdef" * {}, "cdofhij" * {})'.format(v, size, size),
                                 globals=globals(),
                                 setup='gc.collect(); gc.enable()',
                                 number=10),
                ('danieljour', 'mateus', 'aries', 'reti'))
    print(size, '\t', '\t'.join(map(str, times)))

Answer 3

Code review:

Apart from Daniel Jour's advice

if len(igual) > len(resposta):
      resposta = igual

This part of logic, sorta duplicated with lcs_temp, as len(igual) just equal lcs_temp, so you can just start lcs_temp from len(resposta) + 1 this shall reduce much time, and remove igual using slice string string1[i : i + lcs_temp] and string2[j : j + lcs_temp] to replace it.

While using slice string, you don't need to be afraid of i + lcs_temp > tamanho1 and j + lcs_temp > tamanho2, this won't throw error. So just remove i + lcs_temp < tamanho1 and j + lcs_temp < tamanho2 from while

for i in range(tamanho1):
    for j in range(tamanho2):
        lcs_temp = len(resposta) + 1
        while string1[i : i + lcs_temp] == string2[j : j + lcs_temp]:
            resposta = string2[j:j+lcs_temp]
            lcs_temp += 1
        if len(resposta) == min(tamanho1, tamanho2):
           return len(resposta)

My solution:

Here I have another solution, record all substrings of string1 and string2 in set and use and operation of set to findout those common substring and return the longest substring's length

def contando_sstring_igual(string1, string2):
    def substrings(string):
        substr = set()
        for i in range(len(string)):
            for j in range(i + 1,len(string)+1):
                substr.add(string[i:j])
        return substr
    substr1 = substrings(string1)
    substr2 = substrings(string2)
    return len(max(list(substr1 & substr2), key=lambda x:len(x)))

Time cost analysis:

n = len(string1)

m = len(string2)

Your code:

Best case: \$O(n * m)\$ when \$result = 0\$

Worst case: \$O(n * m ^ 2)\$ when \$result = m\$

(Sorry I am not good at average time cost, I guess your average time should still be \$O(n * m ^ 2)\$.)

After code review:

Best case: \$O(m)\$ when \$result = min(n, m)\$ and common substring from 1st char

Worst case: \$O(n * m)\$

As for the while loop will run at most min(n,m) times in total, so it is a constant (sorry still I am not sure for this, hope someone can help me here)

My code:

Best case and Worst case: \$O(max(n,m) ^ 2)\$

Thus(and I guess ;)) code after review and my solution will be faster than yours