Karp-Rabin算法模板

Karp Rabin 算法是利用hash函数的特性进行字符串匹配的。

KR算法对模式串和循环中每一次要匹配的子串按一定的hash函数求值，如果hash值相同，才进一步比较这两个串是否真正相等

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#define d 256	//字符表中字符数目 
using namespace std;
string s,p;
void RK(int q){
	//assert( s&& p && q > 0 );	//如果传递的有错，则打印提示 
	int m=p.size();
	int n=s.size();
	int p_h=0;	//模式串hash 
	int s_h=0;	//s串hash 
	int h=1;
	for(int i=0;i<m-1;i++)h=(h*d)%q;	//h表示ts+1 = 10(31415 - 10000*3) +2 = 14152中的10000   
	for(int i=0;i<m;i++){
		p_h= ( d * p_h + p[i] ) % q;
		s_h= ( d * s_h + s[i] ) % q;		
	}	//求出开始p_h 和 s_h 
	for(int i=0;i<n-m;i++){
		if(p_h==s_h){
			int j;
			for(j=0;j<m;j++)
				if(s[i+j]!=p[j])break;
			if(j==m)printf("P occurs with shifts: %d\n",i);
		}
		if(i<n-m){
			s_h=(d*(s_h-s[i]*h)+s[i+m])%q;
			if(s_h<0)
				s_h+=q;
		}
	}
}
int main(){
	s="GEEKlmnaS FOR GEEKlmnaS njknaskjdaskjbdkjasbdjas njabijbaslbckjsbfGEEKlmnaS FOR GEEKlmnaS";
	p="GEEKlmna";
	int mod=127;	////需要比s长度大 
	RK(mod);
}