# Find the Index of the First Occurrence in a String
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/find-the-index-of-the-first-occurrence-in-a-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Expedia](https://scaleengineer.com/companies/expedia), [Google](https://scaleengineer.com/companies/google), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Warnermedia](https://scaleengineer.com/companies/warnermedia), [IIT Bombay](https://scaleengineer.com/companies/iit-bombay), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems)
---
## Problem
Given two strings `needle` and `haystack`, return the index of the first occurrence of `needle` in `haystack`, or `-1` if `needle` is not part of `haystack`.

**Example 1:**

**Input:** haystack = "sadbutsad", needle = "sad"
**Output:** 0
**Explanation:** "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

**Example 2:**

**Input:** haystack = "leetcode", needle = "leeto"
**Output:** -1
**Explanation:** "leeto" did not occur in "leetcode", so we return -1.

**Constraints:**

* `1 <= haystack.length, needle.length <= 104`
* `haystack` and `needle` consist of only lowercase English characters.

# Approaches
## Brute-Force using Two Pointers
This is the most straightforward approach. We iterate through the `haystack` with a pointer `i`, and for each position, we try to match the `needle` string. A second pointer `j` is used to iterate through the `needle`.
**Time:** O(n * m) · **Space:** O(1)
**Pros:** Easy to understand and implement.; Requires no extra space.
**Cons:** Inefficient, especially for long strings or cases with many repeated partial matches. Its performance degrades significantly in the worst-case scenarios.
### Explanation
The algorithm iterates through the `haystack` string from the first character up to the last possible starting position for `needle`. The last possible starting point is `haystack.length() - needle.length()`.
For each potential starting index `i` in `haystack`, we check if the substring of `haystack` starting at `i` matches the `needle` character by character.
We use an inner loop to compare `haystack[i+j]` with `needle[j]`.
If all characters of `needle` match, we have found the first occurrence, and we return the starting index `i`.
If an inner loop comparison fails, we break out of it and continue the outer loop from the next starting position `i+1`.
If the outer loop completes without finding a match, it means `needle` is not in `haystack`, so we return -1.
```java
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) {
            return 0;
        }
        if (n < m) {
            return -1;
        }

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i; // Found the needle
            }
        }

        return -1; // Needle not found
    }
}
```
### Algorithm
- 1. Get the lengths of `haystack` (n) and `needle` (m).
- 2. Handle edge cases: if `m` is 0, return 0. If `n < m`, return -1.
- 3. Loop through `haystack` with an index `i` from 0 up to `n - m`.
- 4. Inside the loop, start a second loop with index `j` from 0 to `m - 1` to compare characters.
- 5. Check if `haystack.charAt(i + j)` is equal to `needle.charAt(j)`.
- 6. If a character mismatch is found, break the inner loop.
- 7. After the inner loop, if `j` has reached `m`, it means the entire `needle` was matched. Return the starting index `i`.
- 8. If the outer loop finishes without returning, it means no match was found. Return -1.

## Rabin-Karp Algorithm (Rolling Hash)
The Rabin-Karp algorithm improves upon the brute-force approach by using a hashing function. Instead of comparing strings character by character at each position, it compares the hash values of the `needle` and the current substring of `haystack`. A "rolling hash" technique is used to quickly calculate the hash of the next substring in O(1) time.
**Time:** O(n + m) average, O(n * m) worst-case · **Space:** O(1)
**Pros:** Significantly faster than the brute-force approach on average.; Still maintains a low space complexity.
**Cons:** Worst-case performance can be as bad as brute-force.; Implementation is more complex than brute-force, requiring careful handling of modular arithmetic to prevent overflow and negative results.
### Explanation
The core idea is to compute a hash value for the `needle` and for each substring of `haystack` of the same length.
We first calculate the hash of `needle` and the hash of the first `m` characters of `haystack` (where `m` is the length of `needle`).
If the initial hashes match, we do a character-by-character check to confirm it's not a hash collision. If it's a true match, we return index 0.
Then, we iterate through the rest of the `haystack`. In each step, instead of re-calculating the hash from scratch, we "roll" the hash. This involves mathematically removing the contribution of the character leaving the window and adding the contribution of the new character entering the window. This update is an O(1) operation.
At each position, if the `haystack` substring's hash matches the `needle`'s hash, we perform a full string comparison to be certain. If they match, we return the current index.
If we traverse the entire `haystack` without a confirmed match, we return -1.
```java
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m > n) {
            return -1;
        }
        if (m == 0) {
            return 0;
        }

        long base = 31; // A prime number for the hash calculation
        long mod = 1_000_000_007; // A large prime for modulo to prevent overflow

        long needleHash = 0;
        long haystackHash = 0;
        long power = 1; // To store (base^(m-1)) % mod

        // Calculate initial hashes and the highest power of the base
        for (int i = 0; i < m; i++) {
            needleHash = (needleHash * base + needle.charAt(i)) % mod;
            haystackHash = (haystackHash * base + haystack.charAt(i)) % mod;
            if (i < m - 1) {
                power = (power * base) % mod;
            }
        }

        for (int i = 0; i <= n - m; i++) {
            // Check if hashes match
            if (needleHash == haystackHash) {
                // Double check for collision
                if (haystack.substring(i, i + m).equals(needle)) {
                    return i;
                }
            }

            // Roll the hash for the next window
            if (i < n - m) {
                // Remove leading character
                haystackHash = (haystackHash - (haystack.charAt(i) * power) % mod + mod) % mod;
                // Shift left
                haystackHash = (haystackHash * base) % mod;
                // Add trailing character
                haystackHash = (haystackHash + haystack.charAt(i + m)) % mod;
            }
        }
        return -1;
    }
}
```
### Algorithm
- 1. Define a prime base and a large prime modulus for the hash function.
- 2. Calculate the hash of the `needle` string (`needleHash`).
- 3. Calculate the hash of the first `m` characters of the `haystack` string (`haystackHash`).
- 4. Iterate through `haystack` from `i = 0` to `n - m`.
- 5. In each iteration, compare `haystackHash` with `needleHash`.
- 6. If the hashes are equal, perform a character-by-character comparison of the substring to guard against hash collisions. If they are truly equal, return the current index `i`.
- 7. If not a match, and if there are more characters in `haystack` to check, update `haystackHash` to represent the next substring. This is done in O(1) time by subtracting the term for the first character of the old window and adding the term for the last character of the new window.
- 8. If the loop completes, return -1.

## Knuth-Morris-Pratt (KMP) Algorithm
The KMP algorithm is a highly efficient string searching algorithm that achieves optimal linear time complexity, O(n + m). It cleverly avoids redundant comparisons by preprocessing the `needle` to understand its internal structure of repeating prefixes and suffixes.
**Time:** O(n + m) · **Space:** O(m)
**Pros:** Optimal time complexity, guaranteed to be linear even in the worst case.; Extremely efficient for all types of strings.
**Cons:** The algorithm, particularly the logic for building the LPS array, is complex and can be difficult to understand and implement correctly from scratch.; Requires extra space proportional to the length of the `needle`.
### Explanation
The key to KMP is a pre-computed integer array, often called the Longest Proper Prefix Suffix (LPS) array or failure function. For each position `j` in the `needle`, `lps[j]` stores the length of the longest proper prefix of `needle[0...j]` that is also a suffix of `needle[0...j]`.
**Preprocessing Step:** The LPS array is built in `O(m)` time by iterating through the `needle` itself.
**Searching Step:** We then search through the `haystack` using two pointers, `i` for `haystack` and `j` for `needle`.
When `haystack[i]` and `needle[j]` match, we advance both pointers.
If a mismatch occurs (`haystack[i] != needle[j]`), we don't simply reset `j` to 0. Instead, we consult the LPS array. We set `j = lps[j-1]`. This tells us how many characters of the `needle` we can "shift" forward while still potentially matching the suffix of the part of `haystack` we just saw. Crucially, the `i` pointer (for `haystack`) is *not* moved backward. This avoidance of backtracking in `haystack` is what guarantees linear time performance.
If `j` reaches the end of the `needle` (`j == m`), a match has been found, and we return its starting index `i - j`.
```java
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) {
            return 0;
        }
        if (n < m) {
            return -1;
        }

        // 1. Preprocessing: Build the LPS (Longest Proper Prefix Suffix) array
        int[] lps = new int[m];
        int length = 0; // Length of the previous longest prefix suffix
        int i = 1;
        while (i < m) {
            if (needle.charAt(i) == needle.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        // 2. Searching
        int hayPtr = 0; // pointer for haystack
        int needlePtr = 0; // pointer for needle
        while (hayPtr < n) {
            if (needle.charAt(needlePtr) == haystack.charAt(hayPtr)) {
                needlePtr++;
                hayPtr++;
            }

            if (needlePtr == m) {
                return hayPtr - needlePtr; // Match found
            } else if (hayPtr < n && needle.charAt(needlePtr) != haystack.charAt(hayPtr)) {
                if (needlePtr != 0) {
                    needlePtr = lps[needlePtr - 1];
                } else {
                    hayPtr++;
                }
            }
        }
        return -1;
    }
}
```
### Algorithm
- 1. **Preprocessing:**
  - a. Create an LPS (Longest Proper Prefix Suffix) array of size `m` (length of `needle`).
  - b. Compute the LPS array values. For each sub-pattern `needle[0...i]`, `lps[i]` will store the length of the longest proper prefix that is also a suffix. This step takes `O(m)` time.
- 2. **Searching:**
  - a. Use two pointers, `i` for `haystack` and `j` for `needle`.
  - b. Iterate through `haystack` with `i` and `needle` with `j`.
  - c. If `haystack.charAt(i) == needle.charAt(j)`, increment both `i` and `j`.
  - d. If `j` becomes equal to `m`, a match is found. Return `i - j`.
  - e. If a mismatch occurs (`haystack.charAt(i) != needle.charAt(j)`):
    - If `j` is not 0, it means some prefix was matched. We can skip some comparisons by moving `j` to `lps[j - 1]`.
    - If `j` is 0, it means not even the first character matched, so we just increment `i`.
- 3. If `i` reaches the end of `haystack` without a full match, return -1.

# Solutions
### CSharp

```csharp
public class Solution {
    public int StrStr(string haystack, string needle) {
        for (var i = 0; i < haystack.Length - needle.Length + 1; ++i) {
            var j = 0;
            for (; j < needle.Length; ++j) {
                if (haystack[i + j] != needle[j]) break;
            }
            if (j == needle.Length) return i;
        }
        return -1;
    }
}
```

### Java

```java
class Solution {
public
  int strStr(String haystack, String needle) {
    if ("".equals(needle)) {
      return 0;
    }
    int len1 = haystack.length();
    int len2 = needle.length();
    int p = 0;
    int q = 0;
    while (p < len1) {
      if (haystack.charAt(p) == needle.charAt(q)) {
        if (len2 == 1) {
          return p;
        }
        ++p;
        ++q;
      } else {
        p -= q - 1;
        q = 0;
      }
      if (q == len2) {
        return p - q;
      }
    }
    return -1;
  }
}
```

### JavaScript

```javascript
/** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr =
  function (haystack, needle) {
    const slen = haystack.length;
    const plen = needle.length;
    if (slen == plen) {
      return haystack == needle ? 0 : -1;
    }
    for (let i = 0; i <= slen - plen; i++) {
      let j;
      for (j = 0; j < plen; j++) {
        if (haystack[i + j] != needle[j]) {
          break;
        }
      }
      if (j == plen) return i;
    }
    return -1;
  };

```

### CPP

```cpp
class Solution {
private:
  vector<int> Next(string str) {
    vector<int> n(str.length());
    n[0] = -1;
    int i = 0, pre = -1;
    int len = str.length();
    while (i < len) {
      while (pre >= 0 && str[i] != str[pre])
        pre = n[pre];
      ++i, ++pre;
      if (i >= len)
        break;
      if (str[i] == str[pre])
        n[i] = n[pre];
      else
        n[i] = pre;
    }
    return n;
  }

public:
  int strStr(string haystack, string needle) {
    if (0 == needle.length())
      return 0;
    vector<int> n(Next(needle));
    int len = haystack.length() - needle.length() + 1;
    for (int i = 0; i < len; ++i) {
      int j = 0, k = i;
      while (j < needle.length() && k < haystack.length()) {
        if (haystack[k] != needle[j]) {
          if (n[j] >= 0) {
            j = n[j];
            continue;
          } else
            break;
        }
        ++k, ++j;
      }
      if (j >= needle.length())
        return k - j;
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def strStr(self, haystack: str, needle: str) -> int: n, m = len(haystack), len(needle) for i in range(n - m + 1): if haystack[i: i + m] == needle: return i return - 1

```