学步园

算法导论第３２章

题目:pku1961, pku2406, pku2752

首先举个例子:要在一个字符串中找到和ababaca匹配的字符串的个数.

b a c b a b a b a
a b c b a b

            a b a b aca

在这里前面有５个已经匹配成功,第六个不成功.

通过观察可以知道,并不需要往后面移动一个位置继续比较,实际上可以直接移动两个位置比较.

a b a b a c a

      a b a b a c a 

如果移动一个位置,可以看到a,b不相等,再移动一个位置,把前面三个相等的比较下,再比较第四个,当然这就多出了很多时间,也做了很多不必要的工作.

可以通过先计算出前缀函数,就不必做多余的计算了.这样就达么了O(n)的时间复杂度.

void kmp_matcher(char *T, char *P)
{
    n = length(T);
    m = length(P);
    @ = compute_prefix_function(P);
    q = 0;
    for (int i = 1; i < n; i++)
    {
        while (q > 0 && P[q+1] != T[i])
            q = @[q];
        if (P[q+1] == T[i])
            q = q+1;
        if (q == m)
        {
            cout << "find one";
            q = @[q];
        }
    }
}

char *compute_prefix_function(char* P)
{
    m = length[P];
    @[1] = 0;
    k = 0;
    for (q = 2; q < m; q++)
    {
        while (k > 0 && P[k+1] != P[n])
        {
            k = @[k];
        }
        if (P[k+1] == P[q])
            k = k+1;
        @[q] = k;
    }
    return @;
}