Find the First Occurrence in a String

Q: What is the time complexity of finding the first occurrence of a string?

Checking every start position takes O(n · m) time in the worst case, where n and m are the lengths of the haystack and the needle, and O(1) extra space. The Knuth-Morris-Pratt algorithm takes O(n + m) time and O(m) space for its table, whatever the letters are.

EasyArrays and strings Two pointers

+10

You get two strings, haystack and needle. Return the index in haystack where the first copy of needle starts, counting from 0. If needle never appears in haystack, return -1. Write the search yourself instead of calling a built-in substring search such as find or indexOf.

Function

strStr(haystack: string, needle: string) → integer

haystackstring: the text to search in
needlestring: the string to look for
Returnsinteger: the index where the first copy of needle starts, or -1 if there is none

Constraints

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Both strings contain only lowercase English letters.
needle may be longer than haystack. Then it cannot appear, and the answer is -1.

Examples

Input: haystack = "bananarama"needle = "ana"
Output: 1
Explanation: The letters at indices 1, 2 and 3 spell ana. A second copy starts at index 3 and overlaps the first one, but the answer is the first copy, so it is 1.

Input: haystack = "pineapple"needle = "apples"
Output: -1
Explanation: apple starts at index 4, and the haystack ends right after it, so the final s of the needle has no letter to match. No full copy of apples exists, so the answer is -1.

Input: haystack = "abcabcabd"needle = "abcabd"
Output: 3
Explanation: The attempt at index 0 matches five letters, abcab, then meets a c where the needle wants a d. The copy that works starts at index 3 and ends with the final d.

+16 hidden tests on Submit

Follow-up

Can you return every index where needle starts, overlapping copies included, still in O(n + m) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Comparing needle at every start position is correct, but slow when matches almost succeed: a long partial match that fails near its end is thrown away, and the next start reads most of the same letters again. The Knuth-Morris-Pratt algorithm keeps that work. A table built from needle alone says how much of a failed partial match can still be used, so the scan never moves backwards in haystack and finishes in O(n + m).

Check every start position

Correct, but does not finish on the largest tests

Intuition

Call the lengths n for haystack and m for needle. A copy of needle can start at any index from 0 to n-m. Try those starts from left to right. At each one, compare the needle with the haystack letter by letter and stop at the first difference. The first start where all m letters agree is the answer, and going left to right makes it the first copy.

The last start is n-m because a copy that starts later would run past the end of haystack. The same bound handles a needle longer than the haystack: there is no start to try, and the loop falls through to -1.

The cost shows when most letters agree. Take a haystack of 50,000 as and a needle of 24,999 as followed by a b. Each of the 25,001 starts compares 25,000 letters before it reaches the b, which is over 6 × 10^8 comparisons for an answer of -1.

Algorithm

Let n and m be the lengths of haystack and needle.
For each start from 0 to n-m, set j to 0.
While j < m and haystack[start + j] equals needle[j], increase j.
If j reached m, every letter matched: return start.
If no start works, return -1.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Knuth-Morris-Pratt

Intuition

Look at what the brute force throws away. Searching abcabd in abcabcabd, the attempt at index 0 matches abcab and then fails. Those five letters end in ab, and ab is also how the needle begins. So after the mismatch, two letters of the next useful attempt are already matched, and you can carry on from the same spot in the haystack.

A border of a string is a shorter prefix that is also a suffix, like ab in abcab. Before the search, build a table lps where lps[i] is the length of the longest border of needle[0..i]. For abcabd it is [0, 0, 0, 1, 2, 0]. The table depends only on the needle, and you build it with the same matching loop, run on the needle against itself.

Then scan the haystack once and keep k, the number of needle letters matched so far. If the next letter equals needle[k], k grows by one. If not, set k to lps[k-1] and compare the same letter again, until it matches or k is 0. Dropping to a border never skips a copy: any copy that starts inside the failed attempt must begin with a border of what was matched, and the longest border is tried first. When k reaches m, the copy started at i-m+1.

Why this is linear: k rises by at most one per haystack letter, and every fallback lowers it. It cannot fall more times than it rose, so the scan takes at most 2n steps, and building the table takes at most 2m.

Algorithm

Build lps: with k = 0, for each i from 1 to m-1, fall back with k = lps[k-1] while k > 0 and needle[i] differs from needle[k]; if they match, increase k; store lps[i] = k.
Reset k to 0 and walk the haystack with index i.
While k > 0 and haystack[i] differs from needle[k], set k = lps[k-1].
If haystack[i] equals needle[k], increase k.
If k equals m, return i-m+1. If the loop ends, return -1.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

Pitfalls and edge cases

Most bugs sit at the end of the haystack or inside the fallback loop.

Letting the start run up to n-1 instead of n-m. Once the end of the haystack matches the start of the needle, the comparison reads past the end of haystack, which stops Python, Java, Rust and Swift with an index error.
Forgetting that the needle can be longer than the haystack. With unsigned lengths, such as size_t in C++ or usize in Rust, n-m cannot go negative: C++ wraps it around to a huge number, and Rust panics in a debug build. Check m > n first, or compute with signed integers.
Writing the KMP fallback as an if instead of a while. Searching aaa in aabaa, the b needs two fallbacks, from 2 to 1 to 0. Stop after one and k stays at 1 although b matches nothing, and you report a copy at index 2 that does not exist.
Moving the haystack index back after a mismatch in KMP. Only k changes. Rewinding i brings back the O(n · m) worst case.
Returning where the match ends, or a 1-based index. The answer is the start, counted from 0. Lua and R strings start at 1, so subtract 1 before you return.
Declaring strStr at the top level in PHP. PHP function names ignore case, so it clashes with the built-in strstr. The PHP starter puts the function in its own namespace for that reason.

Frequently asked questions4

What is the time complexity of finding the first occurrence of a string?

Checking every start position takes O(n · m) time in the worst case, where n and m are the lengths of the haystack and the needle, and O(1) extra space. The Knuth-Morris-Pratt algorithm takes O(n + m) time and O(m) space for its table, whatever the letters are.

How does the KMP prefix table work?

For every prefix of the needle, the table stores the length of its longest proper prefix that is also a suffix. After a mismatch with k letters matched, those k letters are a prefix of the needle, and lps[k-1] says how many of them can start the next possible copy. For aabaaab the table is [0, 1, 0, 1, 2, 2, 3].

Why not use the built-in find or indexOf?

In production code you should, since it is tested and fast. Interviewers ask for this problem to see you write the matching loop with correct bounds, and the usual follow-up asks how to avoid the O(n · m) worst case. The worst case of a built-in search depends on the language and the library version, so it does not answer that follow-up.

Can you solve it with hashing instead of KMP?

Yes, with the Rabin-Karp algorithm. Compute a hash of the needle and a rolling hash of each window of m letters in the haystack, updating it in constant time as the window slides. Compare letter by letter only when the hashes agree. That runs in O(n + m) expected time, but many hash collisions can push it back toward O(n · m).

Python

def strStr(haystack, needle):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

haystack = "bananarama"
needle = "ana"

Expected