28. Find the Index of the First Occurrence in a String

Posted on Edited on In

28. Find the Index of the First Occurrence in a String

Description

Difficulty: Medium

Related Topics: Two Pointers, String, String Matching

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:

1
2
3
4
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:

1
2
3
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.

Hints/Notes

  • good prime: 9999991
  • get the powHash
  • some edge cases of module operation(like avoid the negative number)

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int strStr(string haystack, string needle) {
        int patHash = 0, left = 0, right = 0, powHash = 1, prime = 9999991, R = 26;
        for (char c : needle) {
            patHash = (patHash * R + (c - 'a')) % prime;
        }
        for (int i = 0; i < needle.size() - 1; i++) {
            powHash = powHash * R % prime;
        }
        int sumHash = 0;
        while (right < haystack.size()) {
            int num = haystack[right++] - 'a';
            sumHash = (sumHash * R + num) % prime;
            if (right - left == needle.size()) {
                if (sumHash == patHash && haystack.substr(left, right - left) == needle) {
                    return left;
                } else {
                    sumHash = ((sumHash - (haystack[left++] - 'a') * powHash) % prime + prime) % prime;
                }
            }
        }
        return -1;
    }
};