String Finding

View as PDF

Submit solution

Points: 5
Time limit: 1.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 T 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
    YouKnowMe  commented on May 5, 2022, 11:28 a.m.

    idk how im getting a TLE bc i cant figure ourt how it is TLEING, can someone help me?


  • -1
    gavin_chen  commented on March 21, 2022, 7:33 p.m.

    why am i getting a value error using (type str).index(type str) but not using (type str).find(type str)?


    • -1
      Spitfire720  commented on March 21, 2022, 7:59 p.m.

      I assume you're using Python. In that case, the proper syntax is (type list).index(type str). The .find method uses type string.


      • -1
        gavin_chen  commented on March 25, 2022, 7:55 p.m.

        Thanks for that :)


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

    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.


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

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