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 and O(1) extra space, where n and m are the lengths of the haystack and the needle. Knuth-Morris-Pratt takes O(n + m) time and O(m) space for its table.

Q: How do you build the KMP prefix table?

Run the matching loop on the needle against itself. Walk i from 1, keep k as the current border length, fall back with k = lps[k-1] on a mismatch, and store k in lps[i] . For aabaaab the table is [0, 1, 0, 1, 2, 2, 3] .

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 to 3 spell ana. Another copy starts at index 3 and overlaps it, but the first copy counts, so the answer is 1.

Input: haystack = "pineapple"needle = "apples"
Output: -1
Explanation: apple starts at index 4, but the haystack ends right after it, so the needle's final s has nothing to match. The answer is -1.

Input: haystack = "abcabcabd"needle = "abcabd"
Output: 3
Explanation: The attempt at index 0 matches abcab, then meets a c where the needle wants a d. The copy at index 3 matches all six letters.

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

Checking every start position is correct, but a partial match that fails near its end is thrown away and the next start rereads the same letters. The Knuth-Morris-Pratt algorithm keeps that work: a table built from needle says how much of a failed match still counts, so the scan never moves back and runs in O(n + m).

Check every start position

Correct, but does not finish on the largest tests

Intuition

Call the lengths n and m. A copy can start at any index from 0 to n-m; a later start runs past the end. Try the starts from left to right, comparing letter by letter until the first difference. The first full match is the first copy, and a needle longer than the haystack leaves no start to try.

A haystack of 50,000 as and a needle of 24,999 as and then a b give 25,001 starts of 25,000 comparisons each: 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

Searching abcabd in abcabcabd, the attempt at index 0 matches abcab and fails. Those letters end in ab, which is how the needle begins, so the next useful attempt already has two letters matched and you carry on from the same haystack position.

A border of a string is a shorter prefix that is also a suffix, like ab in abcab. lps[i] is the length of the longest border of needle[0..i]; for abcabd it is [0, 0, 0, 1, 2, 0]. After a mismatch with k letters matched, drop k to lps[k-1] and compare the same letter again. No copy is skipped: a copy that starts inside the failed attempt begins with a border of what was matched, and the longest border is tried first.

k rises at most once per haystack letter and every fallback lowers it, so the scan takes at most 2n steps.

Algorithm

Build lps: with k = 0, for i from 1 to m-1, set k = lps[k-1] while k > 0 and needle[i] != needle[k]; on a match increase k; store lps[i] = k.
Reset k to 0 and walk the haystack with index i.
While k > 0 and haystack[i] != 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

Letting the start run to n-1 instead of n-m. When the haystack's end matches the needle's start, the comparison reads past the end.
Computing n-m with unsigned lengths (size_t in C++, usize in Rust) when the needle is longer: C++ wraps to a huge number and Rust panics in a debug build. Check m > n first.
Writing the KMP fallback as an if instead of a while. Searching aaa in aabaa, the b needs two fallbacks; stop after one and you report a false copy at index 2.
Rewinding the haystack index after a mismatch. Only k changes; moving i back brings back O(n · m).
Returning a 1-based index in Lua or R.

Frequently asked questions3

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 and O(1) extra space, where n and m are the lengths of the haystack and the needle. Knuth-Morris-Pratt takes O(n + m) time and O(m) space for its table.

How do you build the KMP prefix table?

Run the matching loop on the needle against itself. Walk i from 1, keep k as the current border length, fall back with k = lps[k-1] on a mismatch, and store k in lps[i]. For aabaaab the table is [0, 1, 0, 1, 2, 2, 3].

Can you solve it with hashing instead of KMP?

Yes, with Rabin-Karp. Keep a rolling hash of each window of m haystack letters, updated in constant time as the window slides, and compare letters only when it equals the needle's hash. That runs in O(n + m) expected time; many collisions push it toward O(n · m).

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

Test #1

Test #2

Test #3

Arguments

haystack = "bananarama"
needle = "ana"

Expected Output