Find The Index of The First Occurrence in a String

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if it does not occur. This is LeetCode 28, the same job as Java's String.indexOf.

Example 1

Input: haystack = "sadbutsad", needle = "sad" Output: 0 Explanation: "sad" occurs at 0 and 6; the first is 0.

Example 2

Input: haystack = "cscodeio", needle = "cscd" Output: -1

How to Think About It

Step 1: Try every starting position

For each start in haystack, compare characters with needle until one differs or the whole needle matches. With n and m the two lengths, this is O(n × m) in the worst case, as in "aaaaaaab" searched for "aab", where almost every start matches for a while before failing.

Step 2: The waste in the simple method

When a comparison fails after matching several characters, the simple method moves the start forward by one and compares those same characters again. But we already know what they are: they are the first characters of the needle.

Step 3: KMP reuses what already matched

Precompute, for every prefix of the needle, the length of its longest part that is both a proper prefix and a suffix (the lps array). For "ABAB", the prefix "ABA" has "A" at both ends, so its value is 1.

After matching j characters and then failing, the last lps[j - 1] matched characters are already the start of the needle. So continue with j = lps[j - 1] without moving back in the haystack at all.

Step 4: Which one to use

The simple method is short and fast on ordinary text. KMP guarantees O(n + m) on any input. KMP String Matching explains how the lps array is built, step by step.

Walkthrough

The simple method on haystack = "sadbutsad", needle = "but".

Start	Compared	Result
0	s vs b	mismatch
1	a vs b	mismatch
2	d vs b	mismatch
3	b = b, u = u, t = t	full match: return 3

Java Solution

strStrSimple is the try-every-start version; strStr is KMP.

Java

public class FindTheIndexOfTheFirstOccurrenceInAString {

    // Simple version: try every starting position
    public static int strStrSimple(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        for (int start = 0; start + m <= n; start++) {
            int j = 0;
            while (j < m && haystack.charAt(start + j) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return start;                 // every character matched
            }
        }
        return -1;
    }

    // KMP: never move backwards in the haystack
    public static int strStr(String haystack, String needle) {
        int m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] lps = new int[m];               // longest proper prefix that is also a suffix
        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(); ) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                if (j == m) {
                    return i - m;
                }
            } else if (j > 0) {
                j = lps[j - 1];               // reuse what already matched
            } else {
                i++;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(strStr("sadbutsad", "sad"));        // 0
        System.out.println(strStr("cscodeio", "cscd"));        // -1
        System.out.println(strStrSimple("sadbutsad", "but"));  // 3
    }
}

The original implementation, IndexOfFirstOccurrenceInAString.java, is on GitHub.

Complexity

Simple: O(n × m) time in the worst case, O(1) space.
KMP: O(n + m) time, O(m) space for the lps array.

The Z-function is another linear-time way to search for a pattern.