该算法计算把每个字符映射至0到d-1之间的整数,从而把字符串看做d进制数,每一个字符串对应的d进制数就是字符串的指纹,两个字符串相等当且仅当它们的指纹相等.这样当把模式串和目标串对应子串匹配时，只需比较它们的指纹是否相等就可判断是匹配成功还是失配。
算法先用霍纳法则和模运算计算模式串和起始目标子串的指纹的模,每次匹配结束后,利用递推关系在常数时间内计算下一个目标子串的指纹的模,每次匹配时,若指纹的模不等，则指纹不等，从而可断定失配,若相等,则仍有可能失配，此时直接比较模式串和目标子串判断是否匹配，然后计算下一个目标子串指纹的模，开始下一轮匹配。在算法运行前需预计算d的m-1次方的模,m是模式串的长度,可用反复平方法快速计算,计算结果在递推计算目标子串指纹的模时会用到.
注意,每次得到目标子串指纹的模时,该要么是非负值mod,要么是mod减去q,(q是选定的素数模数),它们都是指纹除以模数的余数.由于模式串的指纹的模为正值,所以当目标子串的指纹的模为负时，需要将其加上q得到非负余数才能和模式串指纹的模比较
c++代码:
#include<iostream>#include<string>#include<vector>usingstd::vector;usingstd::size_t;usingstd::string;size_tlog2(constsize_t&N){size_t l=0;size_t r=1;while(true){r<<=1;if(r>N)break;++l;}returnl;}longlongrepeatSquare(longlongbase,size_t exp,longlongmode){size_t bit_num=log2(exp);size_t mask=1ull<<bit_num;size_t c=0;longlongd=1;while(mask!=0){c<<=1;d=(d*d)%mode;size_t every_bit=exp&mask;if(every_bit){++c;d=(d*base)%mode;}mask>>=1;}returnd;}voiddoRabinKarp(conststring&pattern,conststring&text,constvector<longlong>&mode_num){if(pattern.empty()||text.size()<pattern.size())return;constlonglongradix=128ll;vector<longlong>exp_mode_result(mode_num.size());for(size_t i=0;i<mode_num.size();++i){exp_mode_result[i]=repeatSquare(radix,pattern.size()-1,mode_num[i]);}vector<longlong>pattern_mode_digit(mode_num.size());vector<longlong>text_mode_digit(mode_num.size());for(size_t j=0;j<mode_num.size();++j){for(size_t i=0;i<pattern.size();++i){pattern_mode_digit[j]=(radix*pattern_mode_digit[j]+static_cast<longlong>(pattern[i]))%mode_num[j];text_mode_digit[j]=(radix*text_mode_digit[j]+static_cast<longlong>(text[i]))%mode_num[j];}}std::cout<<"RabinKarp算法匹配结果:"<<std::endl;for(size_t i=0;i<=text.size()-pattern.size();++i){if(pattern_mode_digit==text_mode_digit){if(pattern==text.substr(i,pattern.size())){std::cout<<"匹配位置:"<<i<<std::endl;}}if(i!=text.size()-pattern.size()){for(size_t j=0;j<mode_num.size();++j){longlongtemp=(radix*(text_mode_digit[j]-static_cast<longlong>(text[i])*exp_mode_result[j])+static_cast<longlong>(text[i+pattern.size()]))%mode_num[j];text_mode_digit[j]=temp<0?temp+mode_num[j]:temp;}}}}intmain(){string text="ababababab";string p="abab";vector<longlong>q={999983,100003};doRabinKarp(p,text,q);return0;}
