+ 1

How make it faster?

Hi, everybody. Is it possible to speed up this code? The task is to print all the coordinates of the occurrence of substring T in string S in one line separated by a space. The code runs 0.218 seconds, and I need to keep within 0.2. S = input() T = input() i = 0 while True: i = S.find(T, i) if i < 0: break print(i, end=' ') i += 1

16th Aug 2019, 2:32 AM
Dmitry Venzik
Dmitry Venzik - avatar
4 Antworten
+ 2
There are two ways of speeding this up. The first one is faster at calculating the result, the second one is faster at printing it. print(" ".join([str(i) for i in range(len(S)-len(T)+1) if T==S[i:i+len(T)]])) i,n,s = 0,T[1:].index(T[0])+1,"" while i<=len(S)-len(T): if T==S[i:i+len(T)]: s += " "+str(i) i += 1 else: i += n print(s[1:-1])
16th Aug 2019, 3:42 AM
Diego
Diego - avatar
+ 1
Diego Not the correct conclusion. Your code displays a list, and you need a line with coordinates separated by a space. Example: if the input is S = abaaaababa and T = aba, then my code output will be "0 5 7" without quotes, your [0, 5, 7]. The result is the same, but the decision on the output format will not pass.
16th Aug 2019, 3:51 AM
Dmitry Venzik
Dmitry Venzik - avatar
+ 1
Diego Good option, thanks! I'll check on him tonight, there's no way at work right now.
16th Aug 2019, 4:00 AM
Dmitry Venzik
Dmitry Venzik - avatar
+ 1
Diego Yesterday I did not have time to check the solution, today I tested it, it turned out 0.156 seconds. Thank you! :) I used the variant with the join method.
17th Aug 2019, 4:15 PM
Dmitry Venzik
Dmitry Venzik - avatar