easy

Find the Index of the First Occurrence

Given a text string and a non-empty pattern, return the index of the first occurrence of the pattern in the text, or -1 if the pattern does not occur.

Constraints

1 ≤ haystack.length, needle.length ≤ 10^4
Lowercase English letters

Examples

in: haystack = "sadbutsad", needle = "sad"

out: 0

in: haystack = "leetcode", needle = "leeto"

out: -1

Recognition clues

Compare a window of length |needle| at each offset
Naive comparison restarts after a mismatch — O(n · m)
Prefix-function or rolling hash avoids re-scanning

Pattern

Sliding Window

A question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.

Naive String Matching Knuth–Morris–Pratt (KMP)Rabin–Karp Z-Algorithm

Solution

The straightforward approach slides a window of length m over the text and compares characters until a mismatch, which is O(n · m) worst case but fine at these sizes. For guaranteed linear time use KMP: precompute the failure table of the pattern (longest proper prefix that is also a suffix for each prefix), then scan the text once, using the table to shift the pattern after a mismatch without moving back in the text.

time O(n + m) with KMP, O(n · m) naivespace O(m)

Alternative approaches

Rabin-Karp compares rolling hashes of each window and verifies on hash match — expected O(n + m) and simple to extend to multiple patterns. The Z-algorithm on needle + "#" + haystack also works.

Code it yourself

Solve in

Hints:

Learn Sliding Window (Fixed Size)▶ Visualize