[C++知识库]Algorithm第四版算法 C++实现(二十八)——Rabin Karp算法（指纹字符串查找算法）

字符串没法直接进行比较，但是数字可以直接进行比较，那我们能不能把字符串转换为数字并比较是否相等呢？答案事肯定的。但是求出其散列表相同的字符串并不一定就相同（如果用的是几何加减法），比如ac和ab，ac和ca，都是相同的。用其他的处理方法也极有可能出现不同字符串相同散列值的情况，所以我们需要对符合匹配的字符串进行检查。

class rabinkarp
{
private:
	std::string pat;	//模式字符串
	long long pat_hash;		//模式字符串的散列值
	int m;		//模式字符串长度
	long long q = 2147483647;	//一个很大的素数
	int r = 256;	//字符表大小
	//long long rm;		//R^(m-1)%q ——书上如是说
	long long hash(std::string key, int m)		//求散列值
	{
		long long h = 0;
		for (int j = 0; j < m; j++)
		{
			h = ( h + key[j]) % q;
		}
		return h;
	}
	bool check(std::string txt,int i)	//检查字符串是否符合
	{
		for (int j = 0; j < m; j++)
		{
			if (txt[j + i] != pat[j])
			{
				return false;
			}
		}
		return true;
	}
public:
	rabinkarp(std::string pat)
	{
		this->pat = pat;
		this->m = pat.length();
		//rm = 1;
		/*
		for (int i = 1; i <= m - 1; i++)
		{
			rm = (r*rm) % q;
		}
		*/
		pat_hash = hash(pat, m);
	}
	int search(std::string txt)
	{
		int n = txt.length();
		long long txt_hash = hash(txt, m);
		//printf("%lld = %lld?\n", pat_hash , txt_hash);
		if (pat_hash == txt_hash)	//一开始就匹配成功
			return 0;
		for (int i = m; i < n; i++)
		{
			//txt_hash = (txt_hash + q - rm * txt[i - m] % q) % q;
			//txt_hash = (txt_hash*r + txt[i]) % q;
			txt_hash = (txt_hash + txt[i] - txt[i - m]);
			printf("loop:%d %lld = %lld?\n",i, pat_hash, txt_hash);
			if (pat_hash == txt_hash)
				if(check(txt,i-m+1))
					return i - m + 1;
		}
	}
};

运行结果

这是很巧妙的方法，对吧~？