实现Horspool算法并在文本“BESS KNEW ABOUT BAOBABS”中查找模式“BAOBAB”输出比较次数的屏幕截图

Question

如题所述

Answer 1

horspool和kmp的思路相似，都是通过预处理模式串来找到失配函数(转移函数)，进而避免重复运算。算法平均时间复杂度是O(N)，但在最坏的情况下，会达到O(MN)。下面的代码打印出了每次转移的结果，方便了解horspool的过程。

#include <bits/stdc++.h>
using namespace std;

const char *text = "BESS KNEW ABOUT BAOBABS";
const char *pattern = "BAOBAB";
int T[256];     // 转移函数

void init(const char *pattern)
{
    int sz = strlen(pattern);
    for(int i = 0; i < 256; ++i) T[i] = sz;
    for(int i = 0; i < sz - 1; ++i) T[pattern[i]] = sz - 1 - i;
}

int calc()
{
    int sz_text = strlen(text), sz_pattern = strlen(pattern);

    int tot = 0;  // 比较次数
    int skip = 0; // 窗口左端点
    while(sz_text - skip >= sz_pattern) {
        // horspool的过程
        printf("%s\n", text);
        for(int i = 0; i < skip; ++i) putchar(' ');
        printf("%s\n\n", pattern);

        int i = sz_pattern - 1;
        while(text[skip + i] == pattern[i]) {
            ++tot; // 比较成功

            if(i == 0) return tot;
            --i;
        }
        ++tot;      // 比较失败

        skip = skip + T[text[skip + sz_pattern - 1]];
    }
    return tot;
}

int main()
{
    // 对pattern进行预处理
    init(pattern);

    // horspool
    printf("%d\n", calc());

    return 0;
}

运行结果：