rk.cpp

RK算法：Rabin Karp string search algorithm,一种高效的字符串搜索算法

/* Rabin Karp string search algorithm */ 
#include <iostream.h> 
#include <string.h> 

unsigned int q = 65521; /* largest prime < 2^16 */ 
unsigned int d = 257;	/* base for numeric interpretation of strings */ 
unsigned int dM;		/* d^(M-1), where M is the length of the pattern */ 

void hash_init(int M){ 
	dM = 1; 
	for (int i = 1; i < M; i++) 
		dM = (dM*d)%q; 
} 
unsigned int hash(char* t, int n){ 
	unsigned h = t[0]; 
	for (int i = 1; i < n; i++) 
		h = (d*h + t[i])%q; 
	return h; 
} 
unsigned int hash_next(char* t, int M, int h){ 
	unsigned int oldest = (dM*t[0])%q; 
	unsigned int oldest_removed = ((h + q) - oldest)%q; 
	return (d*oldest_removed + t[M])%q; 
} 
int equal_string(char* p, char* q, int n){ 
	/* returns "true" if first n characters of p and q are identical */ 
	return n == 0 || ( *p == *q && equal_string(p+1, q+1, n-1)); 
} 
/* 
Rabin-Karp string search. 
returns index of first occurrence of string p in a. 
returns length of a if there is no occurrence of p in a. 
*/ 
int rksearch(char* p, char* a) 
{
	int M = strlen(p); 
	int N = strlen(a); 
	hash_init(M); 
	unsigned int h1 = hash(p, M); 
	cout << h1 << "\n"; 
	unsigned int h2 = hash(a, M); 
	cout << h2 << "\n"; 
	for (char* b = a; b < a + N - M; b++) 
	{ 
		cout << h1 << " " << h2 << " " << equal_string(p, b, M) << " " << b << "\n"; 
		if (h2 == h1 && equal_string(p, b, M)) return b-a; 
		h2 = hash_next(b, M, h2); 
	} 
	return N; 
} 
/* 
tests rksearch 
*/ 
int main() 
{ 
	int index; 
	char* p = "hello"; 
	char* a = "All test programs contain the word hello, bye."; 
	cout << "\nGiven pattern \n\"" << p << "\" and text \n\"" << a << "\"\n"; 
	index = rksearch(p,a); 
	cout << "rksearch returns " << index << "\n"; 
	
	a = "hello, world"; 
	cout << " Given pattern \n\"" << p << "\" and text \n\"" << a << "\"\n"; 
	index = rksearch(p,a); 
	cout << "rksearch returns " << index << "\n"; 
	
	a = "Goodbye, cruel world"; 
	cout << " Given pattern \n\"" << p << "\" and text \n\"" << a << "\"\n"; 
	index = rksearch(p,a); 
	cout << "rksearch returns " << index << "\n"; 
	return 0; 
}