字符串匹配之Sunday算法

缘起

Sunday算法是1990年才发明的. 据说效率比BM、KMP更快的算法. 最重要的还是好理解. BM算法以及下篇文章要讲解的Horspool算法都是后缀匹配算法.但是Sunday算法是前缀匹配算法. Sunday算法的移动并不是依据失配字符， 而是基于即将要参与进行匹配的字符（确切讲是失配字符的后一个字符）. 所以这样会更简洁.

我也很纳闷——Sunday算法这么高效而且简洁，为什么没有早点被人发明?

分析

首先Sunday算法移动的情况是下面这个样子

​ 图1

也就是，Sunday算法移动的基调是——移动文本串.

下图展示了Sunday算法失配的处理的思路

​ 图2

其实很容易使用反证法证明这种移动是没问题的——即不会错失匹配. 否则的话，上图的那个e就不是最右边的. 根据上图，不难写出Sunday算法.

ps: 这里多说一句，为什么要关注那个失配的字符的后一个字符? 因为当前已经失配了，所以肯定要移动文本串，那么文本串的失配字符的后一个字符一定要参与到匹配（从匹配到失配过程中该字符是没有参与到匹配中去的.），但是有一种情况是例外的，就是发生了匹配,则所谓的失配就是文本串的字符和\0字符失配, 这种情况下其实文本串失配的那个字符并没有参与到匹配中的. 所以移动的距离和一般意义下的失配移动的距离是不一样的. 我们说的意思见下图

​ 图3

其实图3已经画出了 Sunday算法的核心了——着眼于文本串的失配字符的下一个字符的匹配（当然，对于普通失配和发生匹配两种情形, “下一个字符”的意义是有区别的，区别在图3中说明了——对于普通失配，”下一个字符”就是真的文本串中的失配字符的下一个字符，对于匹配成功的情形，”下一个字符”就是匹配成功后文本串的下一个字符）.

但是注意，上面所有图中画的都是失配字符后面的一个字符在p中存在的情形, 如果不存在呢? 就要直接越过它. 则移动的距离并不是d,而是m.

举个例子吧，例如T= “GoogleYGoogle” 和 p= “Google”, 则Y不似图3的下半部分, 因为图3的下半部分画的c是在p中，但是这里的例子显然Y不在p中，则是不是要移动m=6呢? 显然是错误的, 应该移动的是6+1=7.

类似的例子是 T=”GoomGoogle”和 p=”Google”, m是普通失配，但是m不在p中, 那是不是文本串左移动移动m=6呢?显然不是, 而是越过’m’. 所以移动的时候还需要根据d的值是不是等于m判断要移动的距离到底是多少. 

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
45
46
47
48
49
50
51
52
53
54
#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 sunday() // 字符串匹配之Sunday算法
{
	for (int i = 0;i<26;i++) d[i] = m; // 预设都是m
	for (int i = 0; i<m; i++) d[p[i]-'a'] = m-i;  // 则如果p中存在多个相同的字符的话,则就会以最右边的字符为准(这样就防止错失匹配)
	int pos = 0; // 我们一直匹配的是 T[pos,...,pos+m-1]和p[0,..,m-1],即pos是T匹配的起点
	while(pos<=n-m)
	{
		int i=0;
		while(p[i]&&T[i+pos] == p[i]) i++; // 最后T[i+pos]!=p[i], 或者p[i]为0, 即T[pos,...,pos+i-1]和p[0,...,i-1]匹配,但是T[pos+i]和p[i]失配
		if (!p[i])
		{
			printf("%d\n",pos); // 找到了匹配
			if (i+pos>=n) break;
			pos += d[T[i+pos]-'a']==m?(m+1):m;
		}
		else // 对于匹配和普通失配, pos的变化是不同的(图3已经说明了这一点)
		{
			if (i+pos+1>=n) break;
			pos+=d[T[i+pos+1]-'a']==m?(i+1):d[T[i+pos+1]-'a'];
		}
		if (pos>n-m) break;
	}
}


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);
	sunday();
	return 0;
}
/*
测试数据
abcdacdaahfacabcdabcda abcda
或者
myGoogleyouGoogleLove Google
*/