# 实现 Sunday 匹配

## 01、实现 strStr()

### 题目：实现 strStr()

实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 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都是这样。

![](../../images/1.f441ca2d.jpg)

而对于SUNDAY算法，我们从头部开始比较，一旦发现不匹配，直接找到主串中位于模式串后面的第一个字符，即下面绿色的 “s”。（这里说明一下，为什么是找模式串后面的第一个字符。在把模式串和目标串对齐后，如果发现不匹配，那肯定需要移动模式串。问题是需要移动多少步。各字符串匹配算法之间的差别也来自于这个地方，对于KMP，是建立部分匹配表来计算。BM，是反向比较计算移动量。对于SUNDAY，就是找到模式串后的第一个字符。因为，无论模式串移动多少步，模式串后的第一个字符都要参与下一次比较，也就是这里的 “s”）

![](../../images/2.fc3a2c47.jpg)

找到了模式串后的第一个字符 “s”，接下来该怎么做？我们需要查看模式串中是否包含这个元素，如果不包含那就可以跳过一大片，从该字符的下一个字符开始比较。

![](../../images/3.af2b4e20.jpg)

因为仍然不匹配（空格和l），我们继续重复上面的过程。找到模式串的下一个元素：t

![](../../images/4.73e083c6.jpg)

现在有意思了，我们发现 t 被包含于模式串中，并且 t 出现在模式串倒数第3个。所以我们把模式串向前移动3个单位：

![](../../images/5.607471fb.jpg)

有内味了，我们发现竟然匹配成功了，是不是很神奇？证明的过程今天暂且不谈（后面我会出一个算法证明篇，来证明之前讲过的一些算法。我需要你做的是，掌握上面这些！）

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

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

## 03、算法应用

自然是把这个算法应用到我们的题目中咯...


根据分析，得出代码：（给一个保证你能看的懂的Golang版本的）

```go
func strStrSunday(haystack, needle string) int {
    //先判断两个字符串的合法性
	if len(haystack) < len(needle) {
		return -1
	}
	if haystack == needle {
		return 0
	}
    //定义最终位置的索引
	index := -1
	i := 0
    //定义目标匹配索引
	needleIndex := 0
	for i < len(haystack) {
        //逐字节判断是否相等
		if haystack[i] == needle[needleIndex] {
            //只有当index为-1时，说明是首次匹配到字符
			if index == -1 {
				index = i
			}
            //主串索引和模式串索引都自增
			i++
			needleIndex++
            //判断是否完成匹配
			if needleIndex >= len(needle) {
				break
			}
			continue
		}
        //走到这里说明没有匹配成功，将匹配目标索引置为默认
		index = -1
        //计算主串需要移动的位置
		i = i + len(needle) - needleIndex
        //如果主串索引大于了主串实际长度则返回
		if i >= len(haystack) {
			return index
		}
        //计算下一个字符在模式串最右的位置
		offset := 1
		for j := len(needle) - 1; j > 0; j-- {
			if haystack[i] == needle[j] {
				offset = j
				break
			}
		}
        //将主串的索引左移指定长度，使当前的字符和模式串中最右匹配到的字符串对齐
		i = i - offset
        //将模式串的索引重置
		needleIndex = 0
	}
	return index
}

```

## 来源

> [实现 Sunday 匹配](https://www.geekxh.com/1.3.%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%B3%BB%E5%88%97/303.html#_03%E3%80%81%E7%AE%97%E6%B3%95%E5%BA%94%E7%94%A8)