8
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ FYI, this is a common algorithmic problem, you can read about the theory on Wikipedia: Longest Common Substring Problem \$\endgroup\$ – mjul Nov 5 '17 at 16:32
  • 1
    \$\begingroup\$ So ... I'm almost done with the performance related part of my answer. One question though: Which string sizes are you expecting? Hundreds, thousands, millions of characters? \$\endgroup\$ – Daniel Jour Nov 6 '17 at 2:02
  • \$\begingroup\$ @DanielJour The exercise have 250 test cases, that has string from 1 to 100 lengh( and it includes 1 induced EOFError and a empty string that closes the program) and it need to be done in 2 s. I already found an answer but, Ill be glad to get your advise nonetheless \$\endgroup\$ – Mateus Nov 6 '17 at 2:38
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Yours worked, thanks for the very useful advise, the site is Brazilian, so I used portuguese...tho from now on ill always use english no matter what, You never know when you will need help after all \$\endgroup\$ – Mateus Nov 6 '17 at 2:33
  • 1
    \$\begingroup\$ @Mateus I made a change in the search for the substring length from the shortest to longest, which should outperform the previous suggestion in most cases. Thus making it more generally suitable. \$\endgroup\$ – Reti43 Nov 6 '17 at 13:07
11
\$\begingroup\$

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):

quick comparison

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)))
\$\endgroup\$
  • 1
    \$\begingroup\$ Oh thanks, mine IDE (pycharm) says the accepted way is below 120, not 78, I'll keep that in mind next time, Does it make difference on the program efficiency tho? Or is just readability? Also the site is Brazilian, so I used portuguese...tho from now on ill always use english no matter what, You never know when you will need help after all \$\endgroup\$ – Mateus Nov 6 '17 at 2:32
  • \$\begingroup\$ When you update your answer, you may want to take into account a change I made in my answer regarding searching from the shortest to longest substring possible. It'll also be interesting to see what you came up with. \$\endgroup\$ – Reti43 Nov 6 '17 at 13:05
  • \$\begingroup\$ @Daniel Jour Wow, thats an impressive line, excited to see whats your code. \$\endgroup\$ – Mateus Nov 8 '17 at 7:40
7
\$\begingroup\$

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

\$\endgroup\$
  • 7
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Phrancis Nov 5 '17 at 12:44
  • \$\begingroup\$ @Phrancis Good advice^^ I shall explain my reasoning \$\endgroup\$ – Aries_is_there Nov 5 '17 at 13:32
  • \$\begingroup\$ Thanks for the very useful analysis, but it still wanst enough, it finished the absurdly long test cases in 2.234 s, it needed to be in 2s (no wonder this relatively simple problem is on advanced tab) But thanks you helped a lot. \$\endgroup\$ – Mateus Nov 6 '17 at 2:30

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.