Problem 35.1 · Advanced String AlgorithmsEasy

Find the Index of the First Occurrence in a String

PatternString Matching (KMP, Z, Rolling Hash)

What it teaches: KMP end to end: build lps, then scan the text once.

Practise it on judges as “Find the Index of the First Occurrence in a String”.

In plain words

You're looking for a word inside a long sentence. The simple way restarts from scratch after every mismatch. KMP is smarter: before searching, it studies the word to learn how much of a partial match can be reused, so the pointer in the sentence never has to move backwards.

Return the index where needle first appears in haystack, or −1. Example: haystack = "sadbutsad", needle = "sad" → 0.

The problem

Return the index of the first occurrence of needle in haystack, or −1.

Example 1

Input: haystack = "sadbutsad", needle = "sad"
Output: 0

Example 2

Input: haystack = "leetcode", needle = "leeto"
Output: -1

Constraints

1 ≤ lengths ≤ 10⁴

Pattern clues in the wording

→ Find a substring

These clues point to String Matching (KMP, Z, Rolling Hash): Find a pattern inside a text in linear time by reusing what earlier comparisons already proved, or by comparing hashes instead of characters.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int strStr(String haystack, String needle) {
        return -1;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	haystack = "sadbutsad" needle = "sad"	0
2	haystack = "leetcode" needle = "leeto"	-1
3	haystack = "mississippi" needle = "issip"	4

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Brute force · O(n × m)2. KMP · O(n + m)

Brute force

Time O(n × m) Space O(1)

Try every start and compare.

Approach 1

class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i + needle.length() <= haystack.length(); i++)
            if (haystack.startsWith(needle, i)) return i;
        return -1;
    }
}

Verdict: Fine for small inputs; String.indexOf works similarly.

KMP

Time O(n + m) Space O(m)

Build lps for the needle; scan the haystack with fall-backs; return at the first full match.

▶ Dry run: KMP: lps table, then one passhaystack = "sadbutsad", needle = "sad"

Step 1/4Build lps for "sad": no prefix of it repeats later inside it, so every entry is 0. On a mismatch, the needle would restart at 0.

Approach 2

class Solution {
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        int[] lps = new int[m];
        for (int i = 1, len = 0; i < m; ) {
            if (needle.charAt(i) == needle.charAt(len)) lps[i++] = ++len;
            else if (len > 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        for (int i = 0, j = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = lps[j - 1];
            if (haystack.charAt(i) == needle.charAt(j)) j++;
            if (j == m) return i - m + 1;
        }
        return -1;
    }
}

Verdict: Guaranteed linear.

Before you submit

Edge cases and common mistakes

Test these inputs

Needle longer than haystack
Needle equals haystack

Mistakes people make

Off-by-one in the start index (i − m + 1).

Interview

Follow-up questions

When is brute force actually bad?

Command Palette

The problem

Approaches

Brute force

KMP

Edge cases and common mistakes

Follow-up questions