String Finding (Hard)

Points: 10

Time limit: 2.0s

Memory limit: 64M

Author:

Problem type

You have a string (indexed from $0$ ~0~) with no more than $10^6$ ~10^6~ lowercase characters. Find the first occurrence of a string $T$ ~T~ $(1 \le |T| \le |S| \le 10^6)$ ~(1 \le |T| \le |S| \le 10^6)~, or print -1 if is not a substring of $S$ ~S~.

Input Specification

The first line will have the string $S$ ~S~.
The second line will have the string $T$ ~T~.

Output Specification

Print the index of the first occurrence of the string $T$ ~T~ in $S$ ~S~, or -1 if it is not a substring of $S$ ~S~.

Sample Input

higuyshowsitgoinghiguys
higuys

Sample Output

Comments

3

kingW3 commented on July 8, 2018, 1:44 p.m.

Not sure if my submission should pass it's kinda hacky.

2

Kirito commented on July 8, 2018, 9:02 p.m.

Time to add more test cases I guess...

-123

Hyper commented on March 7, 2018, 10:43 a.m. ← edited →

Is it possible to create a solution for test case # 15 under the time limit using Java 8?

This comment is hidden due to too much negative feedback. Click here to view it.

6

Jerry_Gu commented on Oct. 31, 2018, 7:09 p.m.

is this the most disliked comment?
0

Kirito commented on March 7, 2018, 5:40 p.m.

Yes. (Scroll down a bit.)

3

max commented on Nov. 27, 2017, 6:26 p.m.

C++ disabled

I am getting a warning saying that my default language (C++) has been disabled for this question. Could anyone please tell me why this is the case?

2

1419903188 commented on Nov. 27, 2017, 10:56 p.m. ← edited →

Maybe C++17 is disabled but not other versions of C++.

4

max commented on Nov. 28, 2017, 2:58 a.m.

I use C++11 ... it wasn't working ~12 hours ago - it works fine now.

thanks :)

1

aeternalis1 commented on July 7, 2017, 9:57 a.m.

Is it possible to create a solution for test case # 15 using python 3? I can't seem to run it under the time limit.

-2

Kirito commented on July 7, 2017, 11:28 a.m.

Python's builtin find uses Boyer-Moore, which has a worst-case runtime of $\mathcal O(|S| \times |T|)$ ~\mathcal O(|S| \times |T|)~. Rabin-Karp and KMP are two algorithms which have a worst-case runtime of $\mathcal O(|S| + |T|)$ ~\mathcal O(|S| + |T|)~.