Sunday算法

此原理转自其他博客，侵立删
代码为自己写的，希望大家能看懂

原理介绍

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似

只不过Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

• 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
• 否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。

下面举个例子说明下Sunday算法。假定现在要在主串”substring searching”中查找模式串”search”。

• 刚开始时，把模式串与文主串左边对齐：
  

• 结果发现在第2个字符处发现不匹配，不匹配时关注主串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符n）开始下一步的匹配，如下图：
  

• 结果第一个字符就不匹配，再看主串中参加匹配的最末位字符的下一位字符，是’r’，它出现在模式串中的倒数第3位，于是把模式串向右移动3位（m - 3 = 6 - 3 = r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个’r’对齐，如下：
  

• 匹配成功。

  回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高。

算法实现

const int maxNum = 1005;	// 不同的字符个数
int shift[maxNum];	//下标是字符的int型数，对应的内容是该字符在模式串中最后出现的位置 

//Sunday算法 
int Sunday(string s1, string s2) {
	int len1 = s1.length();	//主串长度
	int len2 = s2.length();	//模式串长度 

	if (len1 < len2)
		return -1;

	//初始化shift数组，默认移动- 模式串长度+1 -长度
	for (int i = 0; i < maxNum; i++) {
		shift[i] = len2 + 1;
	}

	//根据模式串预处理shift数组 
	for (int i = 0; i < len2; i++) {
		shift[s2[i]] = len2 - i;
	}

	int i = 0;	//主串“指针” 
	int j;		//模式串“指针” 
	while (i <= len1 - len2) {
		j = 0;

		while (s1[i + j] == s2[j]) {
			j++;

			//当j等于s2的长度len2时，s1中有s2子串
			if (j == len2)
				return i;
		}

		//不匹配则根据shift数组更新i指针
		i += shift[s1[i + len2]];
	}

	//s1中找不到s2子串
	return -1;
}