LeetCode 28題，使用了Boyer-Moore，語言為C++
有兩種規(guī)則，一是 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;
    }
};