设文本串T与模式串P,分别长nm,字符串匹配即为找到所有的有效偏移,使PT中以该偏移出现

后缀重叠定理

假设x, y和z,x, y是z的后缀,如果|x|<|y|,那x是y的后缀;若相等,则x = y.

暴力匹配(brute force)算法

通过循环的方法,对共计n - m + 1个可能的s值进行检测,成功则返回位置,时间复杂度为$O((n - m + 1) m)$

NaiveStringMatcher(T, P)
n = T.length
m = P.length
for s = 0 to (n - m)
    if P[1..m] == T[s + 1..s + m]
        return true
int BruteForce(char* T, char* p)
{
    int tLen = strlen(t);
    int pLen = strlen(p);
  
    int i = 0;
    int j = 0;
    while (i < tLen && j < pLen)
    {
        if (t[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {   
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == pLen)
        return i - j;
    else
        return -1;
}

Rabin-Karp算法

预处理时间为$\Theta(m)$,最坏情况 下的运行时间为$\Theta((n - m + 1)m)$

算法导论上的介绍十分复杂,总结一下就是通过计算与模式串长度相同的字符串hash来进行匹配,如果hash不同自然不匹配.

如果我们不考虑计算时数据大小,那我们可以通过去掉高位数字加入低位数字的方式来进行偏移,因而可以用$\Theta(m)$内计算出模式串的hash值$p = P[m] + M*(P[m - 1] + M * (P[m - 2]+ ... + M * (P[2] + M * P[1])...))$,同时在$\Theta((n - m + 1)m)$的匹配时间内找到所有的合理偏移.

R-K算法之所以能达到如此小的时间复杂度,原因在于假设

$$s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]$$

是$O(1)$的

如果值过大,我们采用取模的方法来减小值的大小,一般我们选择一个大质数,例如$10^{9} + 7$或者$10^{9} + 9$.

显然,如果结果不相等,可以断定这是无效偏移,如果相等则无法判断,此时我们为了判断这是一个有效偏移亦或是一个伪命中点,采用直接匹配的方式即可,这也是我们选择一个大质数的原因,因为这样可以减少产生伪命中点的概率.

总之,期望匹配时间为$O(n)$.

RabinKarpMatcher(T, P, d, q)
n = T.length
m = P.length
h = d^(m - 1) mod q
p = 0
t0 = 0
for i = 1 to m   //preprocessing
    p = (dp + P[i]) mod q
    t0 = (dt0 + T[i]) mod q
for s = 0 to (n - m)  //matching
    if p == ts
        if P[1...m] == T[s+1...s+m]
            return true
    if s < n-m
        t(s+1) = (d(ts - T[s+1]h) + T[s+m+1]) mod q
void RabinKarpMatcher(char pat[], char txt[], int q)
{
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0;
    int t = 0;
    int h = 1;
 
    for (i = 0; i < M-1; i++)
        h = (h*d)%q;

    for (i = 0; i < M; i++)
    {
        p = (d*p + pat[i])%q;
        t = (d*t + txt[i])%q;
    }
 
    for (i = 0; i <= N - M; i++)
    {
        if ( p == t )
        {
            for (j = 0; j < M; j++)
            {
                if (txt[i+j] != pat[j])
                    break;
            }
            if (j == M)
                printf("Pattern found at index %d \n", i);
        }

        if ( i < N-M )
        {
            t = (d*(t - txt[i]*h) + txt[i+M])%q;
            if (t < 0)
            t = (t + q);
        }
    }
}