字符串匹配之Horspool算法

缘起

【1】中我们介绍了一种很优秀的Sunday算法进行字符串匹配. 它是基于前缀匹配的, 但是改进了BM算法的坏字符规则. 这里介绍后缀匹配算法的第三种——Horspool算法. 基于后缀匹配. 而且也是改进了BM算法的.

分析

Horspool算法的原理图可以用下面一张图片说完

​ 图1

假设在进行后缀匹配的时候, α与σ失配，这时考虑后缀窗口的最后一个字符β. 让模式串安全的移动.

注意，β未必是固定的（不要以为总是模式串p的最后一个字符, 因为万一后缀匹配伊始就失败了呢?）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "stdafx.h"
#include <iostream>
#include <cstring>
#define LOCAL
using namespace std;

const int MAX_T = 255, MAX_P = 20;

char T[MAX_T], p[MAX_P]; // 0索引用于存储数据

int n,m, d[26]; // d[i]表示 'a'+i  距离p的最右端的最近距离（为什么说最近，因为p中可能存在多个相同字符,例如google，则'g'字符距离p的最右端的距离就是3=m-3，而不是6-0=6）

void horspool()
{
	for (int i = 0; i< 26;i++) d[i] = m;
	for (int i=0; i<m-1;i++) d[p[i]-'a']=m-i;  // 初始化，注意, p[m-1]不需要考虑, 因为p[m-1]总是要脱离的.
	int pos = 0;
	while(pos<=n-m) // 比较 T[pos,...,pos+m-1]和p[0,...,m-1], 即pos是比较的起点
	{
		int j = m-1;
		while(~j&&T[pos+j]==p[j]) j--;
		if (!~j) printf("%d\n", pos); // 匹配成功
		pos+=d[T[pos+m-1]-'a']-1; // 要为 T[pos+m-1](即图1中的β)找到匹配的字符.则文本串就需要左移,注意, 这里要写T[pos+m-1]而不是p[m-1],因为后缀匹配可能一开始就失败, 所以p[m-1]和T[pos+m-1]是未必相等的
	}
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s%s", T, p);
	n = strlen(T), m = strlen(p);
	horspool();
	return 0;
}
/*
测试数据
abcdacdaahfacabcdabcda abcda
或者
myGoogleyouGoogleLove Google
*/

其实Horspool算法是字符串匹配中最为写起来最简单的一种算法.

Horspool算法复杂度

假设主串的长度为n,模式串的长度为m，那么Horspool算法最坏情况下的时间复杂度是O(mn)，但平均情况下它的时间复杂度是O(n)。

参考

【1】https://yfsyfs.github.io/2019/07/08/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E4%B9%8BSunday%E7%AE%97%E6%B3%95/