字符串匹配值Sunday算法

实现strStr（）

示例1：

输入: haystack = "hello", needle = "ll"
输出: 2

示例2：

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
02、Sunday 匹配

Sunday 算法是 Daniel M.Sunday 于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。

因为该问是字符串匹配篇第一讲，所以先普及几个概念：

• 串：串是字符串的简称 空串：长度为零的串称为空串
• 主串：包含子串的串相应地称为主串
• 子串： 串中任意个连续字符组成的子序列称为该串的子串
• 模式串：子串的定位运算又称为串的模式匹配，是一种求子串第一个字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式串。

了解这些基本概念，回到这个算法。Sunday匹配不是说这人在周末发现了这个算法，而是这人名字叫星期天（可能父母总加班，所以起了这么个名）。听起来牛叉的不得了，其实是个啥意思：

假若我们的目标串为：Here is a little Hao
模式串为：little

一般来讲，字符串匹配算法第一步，都是把目标串和模式串对齐。不管是KMP，BM，SUNDAY都是这样。

捞干货，这个过程里我们做了一些什么：

• 对齐目标串和模式串，从前向后匹配
• 关注主串中位于模式串后面的第一个元素（核心）
• 如果关注的字符没有在子串中出现则直接跳过
• 否则开始移动模式串，移动位数 = 子串长度 - 该字符最右出现的位置(以0开始)

03、算法应用
下面给出该算法的C++实现

class Solution {
public:
	int strStr(string haystack, string needle)
		/* implementation of Sunday (Daniel M.Sunday. 1990) algorithm */
	{
		bulidMap(needle);
		int i = 0;
		int n = needle.size();
		while (i < haystack.size()) {
			int rv = match(haystack, i, needle);
			/* found a ans */
			if (rv != -1) {
				return rv;
			}
			/* not match otherwise */
			if (i + n >= haystack.size()) break;
			char ch_next = haystack[i + n];
			/* calculate move steps */
			int move = 1;

			int lastOccurIndx = indexOf(ch_next);
			if (lastOccurIndx == -1) move = needle.size() + 1;  /* case1: next char not occured int pattern str */
			else move = needle.size() - lastOccurIndx;          /* case2: otherwise */
			i += move;
		}
		return -1;
	}
private:
	// unordered_map<int, int> _map;
    int _map[26];
	inline void bulidMap(const string patStr) {
        for(int i = 0; i < 26; i++) _map[i] = -1;

		for (int i = 0; i < patStr.size(); i++) {
			_map[patStr[i]-'a'] = i;
		}
	}

	inline int indexOf(char target) 
    /* index of char target in pattern str */ 
    {
        return _map[target-'a'];
	}

	inline int match(const string str, int start, const string pat) 
	/* tell weather pat is a substr of str begining at position `start`*/
	{
		int i, j = 0;
		for (int i = start; i < str.size(); i++) {
			if (str[i] != pat[j++]) return -1;
			if (j == pat.size()) break;
		}
		if (j != pat.size()) return -1;
		// they matched at pos: start
		return start;
	}
};