String Finding (Hard)

View as PDF

Submit solution


Points: 10
Time limit: 2.0s
Memory limit: 64M
Author:

Problem type

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

Input Specification

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

Output Specification

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

Sample Input

higuyshowsitgoinghiguys
higuys

Sample Output

0

Comments


  • 2
    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...


  • -100
    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|). Rabin-Karp and KMP are two algorithms which have a worst-case runtime of \mathcal O(|S| + |T|).


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

    rejudging?


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

      New cases were added to fail incorrect submissions.