String Finding (Hard)

View as PDF
Submit solution
Points: 10
Time limit: 2.0s
Memory limit: 64M
Author:
Kirito
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...


  • -112
    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?


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

      is this the most disliked comment?


    • 1
      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|).