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


  • 1
    SeanJxie  commented on Nov. 6, 2019, 11:42 p.m. ← edited

    I don't see any problem with my code... maybe I'm understanding the question wrong? Pleasehelp Edit: Nvm there's a problem with my code.


    • 0
      Brick99  commented on Nov. 7, 2019, 9:59 a.m.

      the time complexity of your algorithm is to big


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


  • -149
    Hyper  commented on March 7, 2018, 10:43 a.m. ← edited

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


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

      is this the most disliked comment?


      • 0
        CheezWhiz  commented on March 31, 2019, 9:13 p.m.

        probably


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


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