How to speed this code

[wiktor_12341232]

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

 

[WhiteCube]

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.

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.

 

[abdullahn52]

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.

 

[menator01]

Not really sure what your after but, you could just do comparison. For more than one occurrence you could use a regrex

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

yes, ABB is in AABB
No, ABBA is not in AABB