28. Find the Index of the First Occurrence in a String E ！！！需要动手写

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.

A:

就是Rabin-Karp string matching algorithm 来过滤。 有个KMP 算法，太难了，不考虑

我靠，还是出了好多处错误。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = needle.size(), n = haystack.size();
        if(m > n){
            return -1;
        }
        // find a prime number to speed up , 797 is another good choice
        int prime = 3319;
        int vN = 0, vM = 0, rm = 1;// remainder of first letter position
        for(int i =0; i<m;i++){
            vN = (vN * 26 + (needle[i] - 'a')) % prime;
            vM = (vM * 26 + (haystack[i] - 'a')) % prime;
            if(i<m-1){
                rm = (rm*26) % prime;
            }
        }
        if(vN == vM && haystack.substr(0,m) == needle){
            return 0;
        }
        for(int i = m; i<n;i++){
            vM = (( vM - (haystack[i-m] -'a') * rm) * 26 + (haystack[i]-'a') )% prime;
            vM = (vM % prime + prime) % prime; // this is NEEDED, since VM can be negative. fuck
            if(vN == vM && haystack.substr(i-m+1, m) == needle){
                return i-m+1;
            }
        }
        return -1;
    }
};

最经典，也是下次还是容易犯错的：

就是 

            if(i<m-1){
                rm = (rm*26) % prime;
            }

这个一开始没想到。 确实是水平不行 阿。