How to speed this code

Joined
Nov 16, 2022
Messages
1
Reaction score
0
This is the instruction:
You are given two strings. Check, whether second one (called pattern) is a substring of the first one.

Input Format

First line contains string s.

Second line contains string p - pattern.

Constraints
len(s), len(p)<= 1 000 000


Output Format
YES or NO


Sample Input 0

AABB
ABB
Sample Output 0

YES
Sample Input 1

AAABBB
BBBAAA
Sample Output 1

NO
Sample Input 2

AABBABA
BBAA
Sample Output 2

NO




I wrote this but its to slow:

s1 = input()
s2 = input()

k = ''
for i in range(len(s1)):
k = s1
for j in range(i+1,len(s1)):

k += s1[j]

if s2 == k:
break
if s2 == k:
break


if s2 == k:
print("YES")
else:
print("NO")
 
Joined
Sep 21, 2022
Messages
120
Reaction score
15
This is the instruction:
You are given two strings. Check, whether second one (called pattern) is a substring of the first one.

Input Format

First line contains string s.

Second line contains string p - pattern.

Constraints
len(s), len(p)<= 1 000 000


Output Format
YES or NO


Sample Input 0

AABB
ABB
Sample Output 0

YES
Sample Input 1

AAABBB
BBBAAA
Sample Output 1

NO
Sample Input 2

AABBABA
BBAA
Sample Output 2

NO




I wrote this but its to slow:

s1 = input()
s2 = input()

k = ''
for i in range(len(s1)):
k = s1
for j in range(i+1,len(s1)):

k += s1[j]

if s2 == k:
break
if s2 == k:
break


if s2 == k:
print("YES")
else:
print("NO")

The inner loop should stop when k gets longer than s2, that is where the time is wasted.

Creating and comparing every possible substring with s2 is certainly original, but only character comparison is needed.

Code:
pseudocode
Is s2 a substring of s1?
= means assign
== means equal

i1=0
i=0
WHILE ((i1+i)<LEN(s1)) AND (i<LEN(s2))
  IF s1[i1+i]==s2[i] THEN
    i+=1
  ELSE
    i1+=1
    i=0
  END IF
END WHILE
IF i==LEN(s2) THEN
  PRINT YES
ELSE
  PRINT NO
END IF
There is a faster algorithm, but it is quite complicated.

It uses the idea that i1+=1 is not always the best way to restart after a failed character match.
 
Joined
Dec 16, 2022
Messages
1
Reaction score
0
There are a few ways to improve the performance of the code provided in the post. Here are a few suggestions:

The first issue with the code is that it uses a nested loop to check every possible sub-string of s1 to see if it matches s2. This is inefficient, as it has a time complexity of O(n^2) (where n is the length of s1). A more efficient approach would be to use a built-in string method, such as find(), which has a time complexity of O(n).

Another issue with the code is that it continuously reassigns the value of k in the inner loop. This is unnecessary, as the value of k will always be the same for a given iteration of the outer loop.

Here's how the code could be rewritten using the find() method:


s1 = input()
s2 = input()

if s1.find(s2) != -1:
print("YES")
else:
print("NO")


This code has a time complexity of O(n), which is much more efficient than the original code. It simply checks if s2 is a sub-string of s1 using the find() method, and prints "YES" if it is found and "NO" if it is not.

Alternatively, you could use the in operator to check if s2 is a sub-string of s1, like this:


s1 = input()
s2 = input()

if s2 in s1:
print("YES")
else:
print("NO")

This code has the same time complexity as the find() method approach, and is a bit shorter and easier to read.

I hope these suggestions are helpful! Let me know if you have any questions.
 
Joined
Dec 10, 2022
Messages
73
Reaction score
22
Not really sure what your after but, you could just do comparison. For more than one occurrence you could use a regrex

Python:
string1 = 'AABB'
string2 = 'ABB'
string3 = 'ABBA'

if string2 in string1:
    print(f'yes, {string2} is in {string1}')
else:
    print(f'no, {string2} is in {string1}')

if string3 in string1:
    print(f'Yes, {string3} is in {string1}')
else:
    print(f'No, {string3} is not in {string1}')

output
Code:
yes, ABB is in AABB
No, ABBA is not in AABB
 
Last edited:

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,754
Messages
2,569,516
Members
44,991
Latest member
Josephnag

Latest Threads

Top