Help on solving Partial Correct Answer

help
, , , , ,
1

Problem Link: SSCRIPT
My Solutions:

All of these solutions work for the given sample inputs and also work for subtask 1 giving me 30 points. I am guessing my code fails for the subtask 2 with original constraints either due to time complexity issues or inefficient code so could anyone please help. (I am a beginner so I am not that experienced in writing really efficient code or knowing how to handle constraints.)

I have written the code in Python 3.6 and would prefer help in the same however I would also appreciate any help in C++ or Java.
Thanks in advance!

2

The problem you have here is that the matching process implied by pattern in S (or S.find(pattern) ) is inefficient for this very simple pattern once the source and search strings are long.

Instead you could just step through the characters in S counting adjacent * patches (and resetting the count when encountering any other character) and drop out with “YES” if finding a K-length patch, otherwise report “NO”.

1 Like
3

Hi I tried to solve your problem in different ways.

You can check below ac solutions:

AC 1

AC 2 just used in operator

some partial correct:
I expect in this code:

Expected TLE

But i thought in this code it will not occur because it is way optimized Rabin-karp string matching python function

Unexpected TLE.

Tip: In operator is faster than indexing in most of cases especially dealing with sets.