字符串匹配算法之Rabin-Karp算法

关键思想在于把输入的字符既看作图形符号，又看做数字，预处理算出模式P的d进制的值p，时间复杂度为Θ(m)，让后针对n - m + 1个有效偏移s计算出相应的ts,这里是由于利用t_s来计算t_s+1,时间复杂度是Θ(1),因此总的时间复杂度为Θ(n - m + 1)，为了避免p和t_s的值太大，不能在常数时间里计算，引入一个合适的素数q，p和t_s对q取模，这样数就不至于太大，关键的步骤是把p和t_s逐个进行比较找出所有的伪命中点s，再用平凡的比较方法比较P[1..m]和T[s + 1.. s + m]是否相等得到s是否为一个命中点。

该算法的运行时间为O(m) + O(n - m + 1)，最坏情况下为O((n - m + 1)m)，期望的复杂度为O(n)。代码实现为：

#include <iostream>

#include <string>

using namespace std;

int pow_of_d(int d, int m)

{

	int res = 1;

	while(m > 0)

	{

		if(m & 1) res = res * d;

		d = d * d;

		m >>= 1;

	}

	return res;

}

void RABIN_KARP_MATCHER(string T, string P, int d, int q)

{

	int n = T.length();

	int m = P.length();

	int h = pow_of_d(d, m - 1) % q;

	int p = 0;

	int t = 0;

	for(int i = 0; i < m; i++)

	{

		p = (d * p + (P[i] - 48)) % q;

		t = (d * t + (T[i] - 48)) % q;

	}

	for(int s = 0; s <= n - m; s++)

	{

		if(t == p)

		{

			bool flag = true;

			for(int i = 0; i < m; i++)

			{

				if(P[i] != T[s + i])

				{

					flag = false;

					break;

				}

			}

			if(flag)

				cout<<s<<endl;

		}

		if(s < n - m)

		{

			t = ((d * (t - (T[s] - 48) * h) + (T[s + m] - 48)) % q + q) % q;

		}

	}

}

int main()

{

	string T = "2359023141526739921";

	string P = "31415";

	int d = 10;

	int q = 13;

	RABIN_KARP_MATCHER(T, P, d, q);

	return 0;

}

巴特西

字符串匹配算法之Rabin-Karp算法

最新文章

热门文章