AlgoVisual - Interactive Algorithm Visualization

Implement an index_of(s, t) method, which returns the first index where string t appears in string s, or -1 if s does not contain t.

Assume that s has at most $10^5$ characters and t has at most 100 characters.

Example:

Input: s = "hello world", t = "ll"
Output: 2
Input: s = "hello world", t = "abc"
Output: -1

Solution Note: This is a classic problem also known as "string searching." A naive approach checks for t at each index of s. This takes $O(sn * tn)$ time, where sn is the size of s and tn is the size of t, which is good enough given the input size constraints.

There are at least two advanced algorithms to do it more efficiently: the KMP algorithm and the rolling hash algorithm. Both take $O(sn)$ time, which is optimal. Of the two, we find the rolling hash one easier to learn, so we will show it when we talk about hashing.

1def index_of(s: str, t: str) -> int:

2 if not t:

3 return 0

5 for i in range(len(s) - len(t) + 1):

6 match = True

7 for j in range(len(t)):

8 if s[i + j] != t[j]:

9 match = False

10 break

11 if match:

12 return i

14 return -1

String Matching