First Match of a Substring

easy string substring search

Problem

Return the first index in haystack where needle appears, or −1 if it doesn't. The straightforward sweep: at each starting index i of haystack (up to n − m), match needle character by character; on the first complete match, return i.

Inputhaystack = "sadbutsad", needle = "sad"

Output0

"sad" appears at index 0 and again at 6; the first occurrence wins.

haystack

needle

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

function strStr(haystack, needle) {
  const n = haystack.length, m = needle.length;
  if (m === 0) return 0;
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && haystack[i + j] === needle[j]) j++;
    if (j === m) return i;
  }
  return -1;
}

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) return 0;
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
            if (j == m) return i;
        }
        return -1;
    }
}

int strStr(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();
    if (m == 0) return 0;
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && haystack[i + j] == needle[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

Time: O((n − m + 1) · m) Space: O(1)