字符串匹配算法-Sunday

以往不论是上课还是各种资料书上，看到关于字符串匹配的算法，大抵都是KMP了。然而KMP的next数组理解起来颇为费劲，且容易忘记。在LeetCode刷题中偶然发现了一个叫Sunday的算法，不仅容易理解，且经过其他博主测评，Sunday的效率还要高于KMP算法，因此本文记录一下Sunday算法的思路。

参考资料：

1. ​​Sunday 解法
   ​
2. ​​KMP、BM、Sunday、Horspool、strstr字符串匹配算法的性能比较​​

首先briefly陈述一下问题

即获得模式串第一次在目标字符串中出现的位置。

Sunday算法的思想是：

1. 在目标字符串中提取和模式串相同长度的待匹配字符串，并判断该待匹配字符串是否与模式串一致；
2. 若一致，则返回当前待匹配字符串开始的索引即可；
3. 若不一致，那么对待匹配字符串的下一个字符 进行分析，判断它是否出现在模式串中；
4. 若出现了，那么将模式串右移，直到该字符在模式串中最后一次出现的位置和目标字符串中该字符对齐，并进行下一轮迭代；
5. 若没有出现，那么将模式串右移，模式串的第一个字符移动到待匹配字符串的下一个字符 的下一个字符，并进行下一轮迭代；

出于不侵权考虑， 关于示意图请看：https://leetcode-cn.com/problems/implement-strstr/solution/python3-sundayjie-fa-9996-by-tes/

该题C++代码：

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle == "") return 0;
        // 用Sunday算法，比KMP容易理解效率还高
        // 先建立偏移表
        map<char, int> pianyi;
        for(int i = 0; i < needle.size(); i++)
        {
            pianyi[needle[i]] = needle.size() - i;
        }
        // 开始匹配
        for(int i = 0; i < haystack.size();)
        {
            bool is_fit = true;
            for(int j = 0; j < needle.size(); j++)
            {
                if(haystack[i+j] != needle[j])
                {
                    is_fit = false;
                    break;
                }
            }
            if(is_fit)
            {
                return i;
            }
            else
            {
                if(i+needle.size() >= haystack.size())
                {
                    return -1;
                }
                if(pianyi.count(haystack[i+needle.size()]) == 0)
                {
                    i = i + needle.size() + 1;
                }
                else
                {
                    i += pianyi[haystack[i+needle.size()]];
                }
            }
        }
        return -1;
    }
};