LeetCode 28题，使用了Boyer-Moore，语言为C++
有两种规则，一是 Bad Character Heuristic，二是Good Character Heuristic，这里用的是第一种
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle == "") return 0;
int matchSize = needle.size();
if(matchSize > haystack.size()) return -1;
map<char, int> m;
for(int i = 0; i < matchSize; i++){
m[needle[i]] = i;
}
for(int i = 0; i <= haystack.size() - matchSize;){
int step = 0;
for(int j = matchSize - 1; j >= 0; j--){
if(needle[j] != haystack[i + j]){
//bad char can be found in the map
if(m.find(haystack[i + j]) != m.end()){
step = j - m[haystack[i + j]];
step = step > 0 ? step : 1;
}
else{
step = j + 1;
}
break;
}
}
if(step == 0) return i;
i += step;
}
return -1;
}
};
