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
andneedle
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; }
这个一开始没想到。 确实是水平不行 阿。
No comments:
Post a Comment