该算法计算把每个字符映射至0到d-1之间的整数,从而把字符串看做d进制数,每一个字符串对应的d进制数就是字符串的指纹,两个字符串相等当且仅当它们的指纹相等.这样当把模式串和目标串对应子串匹配时只需比较它们的指纹是否相等就可判断是匹配成功还是失配。算法先用霍纳法则和模运算计算模式串和起始目标子串的指纹的模,每次匹配结束后,利用递推关系在常数时间内计算下一个目标子串的指纹的模,每次匹配时,若指纹的模不等则指纹不等从而可断定失配,若相等,则仍有可能失配此时直接比较模式串和目标子串判断是否匹配然后计算下一个目标子串指纹的模开始下一轮匹配。在算法运行前需预计算d的m-1次方的模,m是模式串的长度,可用反复平方法快速计算,计算结果在递推计算目标子串指纹的模时会用到.注意,每次得到目标子串指纹的模时,该要么是非负值mod,要么是mod减去q,(q是选定的素数模数),它们都是指纹除以模数的余数.由于模式串的指纹的模为正值,所以当目标子串的指纹的模为负时需要将其加上q得到非负余数才能和模式串指纹的模比较c代码:#includeiostream#includestring#includevectorusingstd::vector;usingstd::size_t;usingstd::string;size_tlog2(constsize_tN){size_t l0;size_t r1;while(true){r1;if(rN)break;l;}returnl;}longlongrepeatSquare(longlongbase,size_t exp,longlongmode){size_t bit_numlog2(exp);size_t mask1ullbit_num;size_t c0;longlongd1;while(mask!0){c1;d(d*d)%mode;size_t every_bitexpmask;if(every_bit){c;d(d*base)%mode;}mask1;}returnd;}voiddoRabinKarp(conststringpattern,conststringtext,constvectorlonglongmode_num){if(pattern.empty()||text.size()pattern.size())return;constlonglongradix128ll;vectorlonglongexp_mode_result(mode_num.size());for(size_t i0;imode_num.size();i){exp_mode_result[i]repeatSquare(radix,pattern.size()-1,mode_num[i]);}vectorlonglongpattern_mode_digit(mode_num.size());vectorlonglongtext_mode_digit(mode_num.size());for(size_t j0;jmode_num.size();j){for(size_t i0;ipattern.size();i){pattern_mode_digit[j](radix*pattern_mode_digit[j]static_castlonglong(pattern[i]))%mode_num[j];text_mode_digit[j](radix*text_mode_digit[j]static_castlonglong(text[i]))%mode_num[j];}}std::coutRabinKarp算法匹配结果:std::endl;for(size_t i0;itext.size()-pattern.size();i){if(pattern_mode_digittext_mode_digit){if(patterntext.substr(i,pattern.size())){std::cout匹配位置:istd::endl;}}if(i!text.size()-pattern.size()){for(size_t j0;jmode_num.size();j){longlongtemp(radix*(text_mode_digit[j]-static_castlonglong(text[i])*exp_mode_result[j])static_castlonglong(text[ipattern.size()]))%mode_num[j];text_mode_digit[j]temp0?tempmode_num[j]:temp;}}}}intmain(){string textababababab;string pabab;vectorlonglongq{999983,100003};doRabinKarp(p,text,q);return0;}