力扣28题记录C语言rk算法(滚动hash)

力扣28题记录C语言rk算法(滚动hash)

记录的都是做题时的解法这是力扣题，实现strStr()，有很多方法，C语言自带的strstr()函数，BF（暴力匹配），KMP，RK，来记录下RK 。

// rk
#include
#include
int rk(char *s, char *pa){
	unsigned long skey = 0, pakey = 0, base = 1;  
	int slen = strlen(s);
	int palen = strlen(pa);
	for(int i = 0; i < palen; i++){    //计算初始的hash值
		pakey = pakey * 26 + pa[i] - 'a';
		skey = skey * 26 + s[i] - 'a';
		base *= 26;   //base 就是记录模式串第一个字符的次数 比如 ‘cba’ base = pow(26,2)
	}
	int left = 0, right = palen - 1;
	while(right < slen){  // 从第一个依次匹配
		if(skey == pakey){
			return left;
		}
		++right; 
		skey =  skey * 26 - (s[left] - 'a') * base + s[right] - 'a';
		++left;
	}
	return -1;
} 
int main()
{
	char s[]="fhiuwehuewhdhuiqwgdyugqwudguqdfuwqudyguyqwgduq";
	char pa[]="wehuewh";
	printf("%dn",rk(s,pa));
}