Sunday 匹配是啥?

作者:神秘网友 发布时间:2020-10-01 11:14:37

Sunday 匹配是啥?

Sunday 匹配是啥?

前几天的内容大家可能会觉得比较散。这是因为我目前正在筹划背包系列和贪心系列两个主题的内容，所以时间比较紧张，就拿出了之前写的一些题解凑凑数。不过呢，今天我将为大家开启一个新的篇章 - 字符串匹配系列篇，文章写得很用心，相信大家定有所获。

字符串匹配类型的题目，是字符串类型中占比很大的一个支类。


题目：实现 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() 定义相符。

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


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

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

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


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

模式串为：little


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

Sunday 匹配是啥?

而对于SUNDAY算法，我们从头部开始比较，一旦发现不匹配，直接找到主串中位于模式串后面的第一个字符，即下面绿色的 “s”。（这里说明一下，为什么是找模式串后面的第一个字符。在把模式串和目标串对齐后，如果发现不匹配，那肯定需要移动模式串。问题是需要移动多少步。各字符串匹配算法之间的差别也来自于这个地方，对于KMP，是建立部分匹配表来计算。BM，是反向比较计算移动量。对于SUNDAY，就是找到模式串后的第一个字符。因为，无论模式串移动多少步，模式串后的第一个字符都要参与下一次比较，也就是这里的 “s”）
Sunday 匹配是啥?
找到了模式串后的第一个字符 “s”，接下来该怎么做？我们需要查看模式串中是否包含这个元素，如果不包含那就可以跳过一大片，从该字符的下一个字符开始比较。
Sunday 匹配是啥?
因为仍然不匹配（空格和l），我们继续重复上面的过程。找到模式串的下一个元素：
Sunday 匹配是啥?
现在有意思了，我们发现 t 被包含于模式串中，并且 t 出现在模式串倒数第3个。所以我们把模式串向前移动3个单位：
Sunday 匹配是啥?

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


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


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

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


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

//JAVA 
class Solution {
    public int strStr(String origin, String aim) {
        if (origin == null || aim == null) {
            return 0; 
        } 
        if (origin.length() < aim.length()) {
            return -1; 
        }
        //目标串匹配索
        int originIndex = 0;
        //模式串匹配索引
        int aimIndex = 0;
        // 成功匹配完终止条件：所有aim均成功匹配
        while (aimIndex < aim.length()) {
            // 针对origin匹配完，但aim未匹配完情况处理 如 mississippi sippia
            if (originIndex > origin.length() - 1) {
                return -1;
            }
            if (origin.charAt(originIndex) == aim.charAt(aimIndex)) {
                // 匹配则index均加1
                originIndex++;
                aimIndex++;
            } else {
                //在我们上面的样例中，第一次计算值为6，第二次值为13
                int nextCharIndex = originIndex - aimIndex + aim.length();
                //判断下一个目标字符（上面图里的那个绿框框）是否存在。
                if (nextCharIndex < origin.length()) {
                    // 判断目标字符在模式串中匹配到，返回最后一个匹配的index
                    int step = aim.lastIndexOf(origin.charAt(nextCharIndex));
                    if (step == -1) {
                        // 不存在的话，设置到目标字符的下一个元素
                        originIndex = nextCharIndex + 1;
                    } else {
                        // 存在的话，移动对应的数字（参考上文中的存在公式）
                        originIndex = nextCharIndex - step;
                    }
                    //模式串总是从第一个开始匹配
                    aimIndex = 0;
                } else {
                    return -1;
                }
            }
        }
        return originIndex - aimIndex;
    }
}

**调研一下，这种通过题目来讲解知识的方式，大家是否喜欢？**如果喜欢，请留言区扣1。如果不喜欢，请说明理由~


发现网上上来就讲解字符串匹配算法的文章实在是太多了，也不缺我这一个。所以我尝试了这种通过“图解+题目+知识串讲”的形式，文中我也尽可能的减少公式化的东西，让大家能看的进去。希望大家可以给我反馈，如果大家觉得这种形式ok，那么我后面会更高频的去使用这种形式。


所以，今天的问题你学会了吗，评论区留下你的想法！

我把我写的所有题解都整理成了一本电子书，每道题都配有完整图解。点击即可下载

Sunday 匹配是啥?

Sunday 匹配是啥?相关教程

  1. 基于词向量word2vec匹配的英文问答系统

    基于词向量word2vec匹配的英文问答系统 环境准备 python3.6pandas --读取并处理csv文件nltk --http://www.nltk.org/ 自然语言处理工具包，用于分词，词干提取，语料库gensim -- 训练word2vec词向量的工具包 实现过程 导入工具包 import pandas as pd from nlt

  2. MATLAB图像处理之直方图匹配（图像合理增强）

    MATLAB图像处理之直方图匹配（图像合理增强） 先拿结果来看，第一幅是原图 第二幅是直方图均衡化后的图像增强 第三幅是直方图匹配后的处理结果 第二幅 第三幅来看 直接均衡化 会大大增加对比对 但是 有时不符合美观 %直方图匹配 %直方图均衡有时并不能总取得

  3. OpenCV-Python官方教程-16-模板匹配

    OpenCV-Python官方教程-16-模板匹配 模板匹配是用来在一副大图中搜寻查找模版图像位置的方法。OpenCV 为我们提供了函数：cv2.matchTemplate()。和 2D 卷积一样，它也是用模板图像在输入图像（大图）上滑动，并在每一个位置对模板图像和与其对应的输入图像的子

  4. ELK logstash的grok 自带的正则匹配、自定义正则 使用

    ELK logstash的grok 自带的正则匹配、自定义正则 使用 一、使用 1、查看 grok 自带的正则 2、语法 3、使用 1）、Sample Data 2）、Grok Pattern 3）、Custom Patterns 4）、结果 5）、正则讲解 二、在线测试 1、在线Grok Debug工具，Grok校验|调试 2、Kibana

  5. UVA1411 Ants（带权二分图的最大完美匹配、zkw费用流）

    UVA1411 Ants（带权二分图的最大完美匹配、zkw费用流） 题解 #includecstdio#includecstring#includealgorithm#includeiostream#includequeue#includecmathusing namespace std;const int N = 507, M = 200007;const double DINF = 1010580540, eps = 1e-5;in

  6. 【算法拾遗·字符串篇】KMP字符串匹配算法

    【算法拾遗·字符串篇】KMP字符串匹配算法 KMP字符串匹配算法 问题描述 暴力搜索匹配 KMP匹配 图解: 1、构建最长公共前后缀表 2、KMP匹配操作 总结： 代码： 问题描述 已知字符串 text 和 字符串 pattern， 问 pattern 是否为 text 的子串 暴力搜索匹配 int m

  7. 字符串模式匹配（BF--RK--BM--KMP）

    字符串模式匹配（BF--RK--BM--KMP） 目录 BF RK BM 坏字符规则 好后缀规则 KMP next Brute Force，暴力破解，时间复杂度最大为O（mn） bool patternMatching(string pattern, string value) { int m = pattern.size(); int n = value.size(); for(int i = 0;

  8. php 正则匹配中文 乱码问题

    php正则匹配中文乱码的解决办法：首先打开PHP代码文件；然后在代码文件中加上UTF8修饰符即可，其正则表达式的语句如“preg_replace(/[万]/u,萬,$a);”。 推荐：《PHP视频教程》 具体问题： PHP字符串中用正则表达式匹配中文出现乱码 ?phpecho h2正则表达式匹