Rabin-Karp算法原理与实现（模式匹配）

   Rabin-Karp 算法（以下简称为 RK 算法），是基于这样的思路：即把串看作是字符集长度进制的数，由数的比较得出字符串的比较结果。例如，给定字符集为∑ ={0,1,2,3,4,5,6,7,8,9} ，∑长度为 d=10 ，那么任何以∑为字符集的串都可看作 d （此处为 10 ）进制的数。

记模式串 P[0..n-1] 对应的数值为 P ， T[0..n-1] 所有长度为 m 的子串对应的数值为 t_s ，设 P 和 T 都是基于字符集长度为 | ∑ |=d 的字符串。

那么， t_s 即为 T[s..s+m] 对应的数值，这里 0<=s<=n-m-1。

P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))

同样 t₀ 也可类似求得。

最重要的是如何从 t_s 求出 t_s+1 。

t_s+1 =T[s+m]+d*(t_s +d^m-1 *T[s])

注：此处是该算法的关键，即在常数时间内能够计算出下一个 m 长度的字串对应的数值。初看比较抽象，举个例子就比较明白了，设 x=12345 ，现在是已知长度为 3 的数值 234 ，现在要求 345 对应的数值，可以这样来得到： 345 = 5 + 10*(234-10² *2)

   求出所有 m 长度子串所对应的数值，对数值进行比较，继而得出子串是否匹配。当模式串长度很大时，这时对应的数值会很大，比较起来比较麻烦，可使用对一个大奇数取模后进行比较。

C++源代码实现如下：

#include  
#include
#include  
using namespace std;  
 
// get the value of the character in the set   
int getV(char p, string set)  
{  
    for(int i=0; i    {  
        if (p==set[i])  
            return i;  
    }  
    return -1;  
}  
// d is the size of the character set  
int RK(string T, string P,string set)  
{  
    int d = int(set.length());  
    int n = T.length();  
    int m = P.length();  
    int h = pow(double(d), m-1);  
    long int p=0;  
    long int t = 0;  
    for(int i=0; i    {  
        p = d*p + getV(P[i],set);  //P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))
        t = d*t + getV(T[i], set);  
    }  
    for (int s=0; s<=n-m; s++)  
    {  
        cout<<"p,t is "<        if (p==t)  
            return s;  
        if (s            t = getV(T[s+m],set)+d*(t-h*getV(T[s],set));  
    }  
    return -1;  
}  
int main()  
{  
 string set= "0123456789";
 string T,P;
 int i,answer;
 printf("\nRabin-Karp String Searching Program");
 printf("\n====================================");
 printf("\n\nText String --> ");
 cin >> T;
 printf( "\nPattern String --> ");
 cin >> P;

 if ((answer = RK(T, P, set)) >= 0)
 {
  printf("\n");
  cout<  for (i = 0; i < answer; i++)
   printf(" ");
  cout<  printf("\n\nPattern Found at location %d\n", answer);
 }
 else
  printf("\nPattern NOT FOUND.\n");
    return 0;  
}