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

Advertisements

Joined
Sep 21, 2022
Messages
17
Reaction score
2
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.
 

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

Top