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

-81

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?

0

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

Yes. (Scroll down a bit.)

2

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?

1

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

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

3

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

0

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.

0

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|)~.

-9

TypicalToxic commented on April 11, 2017, 11:56 a.m.

rejudging?

11

Kirito commented on April 11, 2017, 12:08 p.m.

New cases were added to fail incorrect submissions.