horspool算法讲解_string匹配字符串

全栈程序员-站长 • 2022年8月21日下午1:36 • 未分类 • 阅读 5

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

Horsepool算法是Boyer-Moore算法的简化版本，这也是一个空间换时间的典型例子。算法把模式P和文本T的开头字符对齐，从模式的最后一个字符开始比较，如果尝试比较失败了，它把模式向后移。每次尝试过程中比较是从右到左的。

假设文本中，对齐模式最后一个字符的元素是c,Horspool算法根据c的不同情况来确定移动距离，无论c是否和模式的最后一个字符相匹配。

一般来说，会存在下面四种情况。

这里写图片描述

情况1：看第一行，模式中不存在c（此时c就是字母A），模式的移动长度就是它的全部长度，移到第二行所示的位置。

情况2：看第二行，c（此时c就是字符O）正好是模式的最后一个字符，但是从右向左比较时，有字符不匹配，比如此时的A和E不匹配。而且模式中的其他m-1个字符也不包含c。移动的情况类似情况1，移动的幅度等于模式的全部长度，移到第三行所示的位置。

这里写图片描述
情况3：看第一行，模式中存在c（此时c就是字符L），但是它不是模式的最后一个字符，移动时应该把模式中最右边的c和文本中的c对齐，移到第二行所示的位置。
情况4：看第二行，c（此时c就是字符O）正好是模式的最后一个字符，但是从右向左比较时，有字符不匹配，比如此时的A和E不匹配。而此时模式中的其他m-1个字符包含c。移动的情况类似情况3，移动时应该把前m-1个字符中最右边的c和文本中的c对齐，移到第三行所示的位置。

这说明，比起蛮力算法每次总是移动一个位置，从右到左的字符比较使模式模式移动得更远。然而，如果在每次尝试时都必须检查模式中的每个字符，它的优势也会丧失殆尽。我们可以预先算出遇到某个字符要移动的距离，并把它存在一个表中。具体来说，对于每一个字符c，可以通过以下公式算出移动距离：

t (c) = {模 式 的 长 度 m 模 式 前 m - 1 个 字 符 中 最 右 边 的 c 到 模 式 最 后 一 个 字 符 的 距 离 （ 如 果 c 不 包 含 在 模 式 的 前 m-1 个 字 符 中 ） （ 其 他 情 况 下 ）

$\begin{align}t(c) =\begin{cases}模式的长度m & \text{（如果c不包含在模式的前m-1个字符中）} \\模式前m-1个字符中最右边的c到模式最后一个字符的距离 & \text{（其他情况下）}\end{cases}\end{align}$

如对于模式BARBER，移动距离如下表所示：

字符c	A	B	E	R	其它字符（包括空格，标点符号，下划线和其它一些特殊字符）
移动距离t(c)	4	2	1	3	6

c++实现

int Horspool(vector<char> & T,vector<char> & P)
{
    int n = T.size();
    int m = P.size();   
    vector<int> table(96,m);//以字母表中可打印字符为索引的数组

    for(int i = 0;i < m - 1;i++)
    {
        table[P[i] - 32] = m - 1 - i;//模式串中每个字符的移动距离，从左至右扫描模式，相同字符的最后一次改写恰好是该字符在模式串的最右边
    }

    int i = m - 1;
    while(i <= n - 1)
    {
        int k = 0;
        while(k <= m - 1 && P[m - 1 - k] == T[i - k])
            k++;

        if(k == m)
            return i - m + 1;//匹配成功，返回索引
        else
            i += table[T[i] - 32];//模式串向右移动
    }

    return -1;//匹配失败
}