字符串匹配,Rabin-Karp算法

朴素的字符串匹配算法为什么慢？ 因为它太健忘了，前一次匹配的信息其实可以有部分可以应用到后一次匹配中的，而朴素的字符串匹配算法只是简单的把这个信息扔掉，从头再来，因此，浪费了时间。好好的利用这些信息，自然可以提高运行速度。

1.问题描述

给定目标字符串 T[0..n-1] （基于 0 的数组，数组长度为 n ），和模式串 P[0..m-1] ，问 P 可否匹配 T 中的任意子串，如果可以，返回匹配位置。

2.问题分析

直观分析

brute-force 的蛮力法，适用于较小规模的字符串匹配。

优化

主要介绍 3 种优化办法，分别具体为： Rabin-Karp 算法，有限自动机和 KMP 算法。将分为 3 篇博文分别讨论。

3.算法描述

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 的子串对应的数值为 ts ，设 P 和 T 都是基于字符集长度为 | ∑ |=d 的字符串。

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

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

同样 t0 也可类似求得。

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

ts+1 =T[s+m]+d*(ts -dm-1 *T[s])

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



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

4.具体实现

这里实现的只是m值较小时的情形，大整数需要特定的类的支持（如可自定义大整数类），选取10进制的数是为了方便起见，当然字母也是OK的。

#include <iostream>
using namespace std;

int getV(char p, const char* set)
{
    for(int i=0; i<strlen(set); i++)
    {
        if (p==set[i])
            return i;
    }
    return -1;
}

int RK(const char* T, const char* P,const char* set)
{
    int base = strlen(set) ;
    int n = strlen(T);
    int m = strlen(P);
    int h = 1;
    for(int i=0;i<m-1;i++)
        h*=base;
    int p = 0;
    int t = 0;
    for(int i=0; i<m; i++)
    {
        p = base*p + getV(P[i],set);
        t = base*t + getV(T[i],set);
    }
    for (int i=0; i<=n-m; i++)
    {
        cout<<"p,t is "<<p<<","<<t<<endl;
        if (p==t) return i;
        if (i<n-m)
            t = getV(T[i+m],set)+base*( t - h*getV(T[i],set) );
    }
    return -1;
}

int main()
{
    // set is the character set
    const char* set= "0123456789";
    const char* T = "258569236589780";
    const char* P = "2365";
    int i = RK(T, P, set);
    cout<<"the postition is:"<<i<<endl;
    return 0;
}