String Finding - Hacking - Olympiads Online Judge

String Finding - Hacking

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 2.0s

Memory limit: 64M

Author:

Kirito

Problem type

To celebrate people complaining that bf4 should have a higher point value, we have created this problem.

You are to print two newline-separated strings $S$ ~S~ and $T$ ~T~ of lowercase English characters, such that $|S|, |T| \le 10^6$ ~|S|, |T| \le 10^6~, and such that calling S.find(T) in Python 2 times out in 10 seconds.

Input Specification

There is no input.

Output Specification

Two newline-separated strings $S$ ~S~ and $T$ ~T~ of lowercase English characters, such that $|S|, |T| \le 10^6$ ~|S|, |T| \le 10^6~, and such that calling S.find(T) in Python 2 times out in 10 seconds.

Note

It is not recommended to submit in Text (the submission size limit is likely too small).

Comments

0

stanwww commented on Oct. 26, 2024, 8:33 p.m.

I need some hints please.

1

dchoo333 commented on Oct. 27, 2024, 5:35 a.m.

Python's builtin .find() is, according to them, a modified version of Boyer-Moore-Horspool algorithm. You're going to obviously want to maximise the length of S, and also maximise the amount of 'checks' that the algorithm has to do.

0

stanwww commented on Oct. 27, 2024, 3:18 p.m. ← edit 4 →

Never mind I got it. I won't disclose my solution too much

3

Kirito commented on Jan. 5, 2023, 9:26 p.m.

I changed the checker to use Python 2 instead of Python 3 and rejudged.