启发式方法1:当模式串m和目标子串g失配(模式串在位置i,目标子串在位置j)时,需要跳转到m在i左侧最近的为g[j]的位置i’,然后从右往左匹配启发式方法2:当模式串m和目标子串g失配(模式串在位置i,目标子串在位置j)时,模式串需要跳转至模式串在i左侧最近的位置j’:m[j’]g[j]且存在j’右侧紧邻j’并且和m[i-1,m.size-1] (即m的后缀子串,该子串的第一个字符的位置索引为i-1) 相等的前缀子串注意这两种启发式方法存在关联,因此我们只需计算当模式串和目标子串在模式串的最右侧失配时启发式方法1所要求的跳转位置和启发式方法2所要求的跳转表但是启发式方法1要求的完整跳转表在boyerMoore算法的简化版本需要用到,所以我们在这里一并计算c代码#pragmaonce#includeiostream#includestring#includevector#includealgorithm#includeunordered_mapusingnamespacestd;voidcomputeNext(conststringpattern_str,vectorintnext){next[0]-1;intj0;intk-1;while(jpattern_str.size()-1){if(k-1||pattern_str[k]pattern_str[j]){next[j]k;}else{if(k0)next[j]0;elseknext[k];}}}voidcomputeOptimalNext(vectorintoptimal_next,vectorintnext,conststringpattern_str){optimal_next[0]-1;for(size_t i1;ioptimal_next.size();i){if(pattern_str[next[i]]pattern_str[i]){optimal_next[i]optimal_next[next[i]];}else{optimal_next[i]next[i];}}}voidKMP_Match(conststringtext_str,conststringpattern){vectorintnext(pattern.size());vectorintoptimal_next(pattern.size());computeNext(pattern,next);computeOptimalNext(optimal_next,next,pattern);size_t i0;size_t j0;size_t count0;while(true){while(itext_str.size()jpattern.size()){if(text_str[i]pattern[j]){i;j;}elseif(j0){i;}else{joptimal_next[j];}}if(jpattern.size()){count;cout第count个匹配结果:endl;cout开始位置i-pattern.size()endl;ii-pattern.size()1;j0;}else{if(count0){coutKMP匹配失败,无匹配结果endl;}break;}}}voidgetCharNearestPresentArray(conststringpattern_str,vectorvectorsize_tchar_nearest_present)//我们只需要char_nearest_present[pattern_str.size()-1]{//但在简化版本中我们需要完整的char_nearest_present所以这里一并计算unordered_mapchar,size_tchar_nearest_pos_map;for(size_t i0;ipattern_str.size();i){for(intj0;j128;j){autorchar_nearest_pos_map.find(static_castchar(j));if(r!char_nearest_pos_map.end()){char_nearest_present[i][j]r-second;}}char_nearest_pos_map[pattern_str[i]]i;}}voidcomputeNearestPosition(conststring_str,vectorvectorsize_tnearest_array){if(_str.size()2)return;string t_str;std::reverse(t.begin(),t.end());vectorintnext(t.size());computeNext(t,next);vectorlistsize_titem_should_check(128,listsize_t());size_t i0;for(size_t k0;k128;k){for(size_t ji2;jnext.size();j){if(next[j]i1t[j]static_castchar(k)){item_should_check[k].push_back(j);}}if(item_should_check[k].empty()false){nearest_array[t.size()-1-i][k]t.size()-1-item_should_check[k].front();}}for(i1;it.size()-2;i){for(size_t k0;k128;k){for(listsize_t::iterator ititem_should_check[k].begin();it!item_should_check[k].end();){if(next[*it]i1){it;}else{ititem_should_check[k].erase(it);}}if(item_should_check[k].empty()false){nearest_array[t.size()-1-i][k]t.size()-1-item_should_check[k].front();}}}}voiddoBoyerMoore(conststringtext_str,conststringpattern_str){if(pattern_str.empty())return;if(text_str.size()pattern_str.size())return;size_t tpattern_str.size()-1;size_t pt;vectorvectorsize_tchar_nearest_present(pattern_str.size(),vectorsize_t(128,pattern_str.size()));vectorvectorsize_tnearest_array(pattern_str.size(),vectorsize_t(128,pattern_str.size()));getCharNearestPresentArray(pattern_str,char_nearest_present);computeNearestPosition(pattern_str,nearest_array);size_t back_index0;size_t temp_ppattern_str.size();size_t temp_t;while(true){size_t tempt;while(true){if(pattern_str[p]!text_str[t]){break;//匹配失败}if(pback_index){if(temp_p!pattern_str.size()){ptemp_p;ttemp_t;back_index0;temp_ppattern_str.size();continue;}break;//匹配成功}--p;--t;}if(pattern_str[p]text_str[t]){cout匹配成功,位置在:tendl;ttemp1;back_index0;}else{intchar_indexstatic_castint(text_str[t]);size_t offset1;if(char_nearest_present[p][char_index]pattern_str.size()){offset1pattern_str.size();}else{offset1pattern_str.size()-1-char_nearest_present[p][char_index];}size_t offset2;if(ppattern_str.size()-1){offset20;temp_ppattern_str.size();back_index0;}elseif(nearest_array[p1][char_index]pattern_str.size()){offset2pattern_str.size();temp_ppattern_str.size();back_index0;}else{offset2pattern_str.size()-1-nearest_array[p1][char_index];//这里offset2必然大于等于offset1back_indexnearest_array[p1][char_index]pattern_str.size()-p;if(nearest_array[p1][char_index]!0){temp_pnearest_array[p1][char_index]-1;temp_tt-1;}else{temp_ppattern_str.size();}}tmax(offset1,offset2);}if(ttext_str.size()){return;}ppattern_str.size()-1;}}intmain(){//string text babbababcab;//string pattern_str babcab;string textabababab;string pattern_strabab;coutKMP算法匹配结果endl;KMP_Match(text,pattern_str);coutBoyerMoore算法匹配结果endl;doBoyerMoore(text,pattern_str);return0;}