专栏首页小浩算法漫画:探索字符串匹配系列 第一讲(Sunday 是个啥玩意)

漫画:探索字符串匹配系列 第一讲(Sunday 是个啥玩意)

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

01

PART

实现 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

PART

Sunday 匹配

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

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

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

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

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

模式串为:little

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

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

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

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

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

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

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

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

03

PART

算法应用

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

根据分析,得出代码:(给一个保证你能看的懂的JAVA版本的)

 1//JAVA
 2class Solution {
 3    public int strStr(String origin, String aim) {
 4        if (origin == null || aim == null) {
 5            return 0;
 6        }
 7        if (origin.length() < aim.length()) {
 8            return -1;
 9        }
10        //目标串匹配索引
11        int originIndex = 0;
12        //模式串匹配索引
13        int aimIndex = 0;
14        // 成功匹配完终止条件:所有aim均成功匹配
15        while (aimIndex < aim.length()) {
16            // 针对origin匹配完,但aim未匹配完情况处理 如 mississippi sippia
17            if (originIndex > origin.length() - 1) {
18                return -1;
19            }
20            if (origin.charAt(originIndex) == aim.charAt(aimIndex)) {
21                // 匹配则index均加1
22                originIndex++;
23                aimIndex++;
24            } else {
25                //在我们上面的样例中,第一次计算值为6,第二次值为13
26                int nextCharIndex = originIndex - aimIndex + aim.length();
27                //判断下一个目标字符(上面图里的那个绿框框)是否存在。
28                if (nextCharIndex < origin.length()) {
29                    // 判断目标字符在模式串中匹配到,返回最后一个匹配的index
30                    int step = aim.lastIndexOf(origin.charAt(nextCharIndex));
31                    if (step == -1) {
32                        // 不存在的话,设置到目标字符的下一个元素
33                        originIndex = nextCharIndex + 1;
34                    } else {
35                        // 存在的话,移动对应的数字(参考上文中的存在公式)
36                        originIndex = nextCharIndex - step;
37                    }
38                    //模式串总是从第一个开始匹配
39                    aimIndex = 0;
40                } else {
41                    return -1;
42                }
43            }
44        }
45        return originIndex - aimIndex;
46    }
47}

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:呕心泣血算法指导篇(真正的干货,怒怼那些说算法没用的人)

    在实际项目中,算法的使用场景有很多,如“Java8中Hashmap使用红黑树来实现”、“Redis底层使用LRU来进做淘汰策略”、“大数据领域很多问题都基于To...

    程序员小浩
  • 漫画:滑动窗口系列 第二讲(无重复字符的最长子串)

    在上一节中,我们使用双端队列完成了滑动窗口的一道颇为困难的题目,以此展示了什么是滑动窗口。在本节中我们将继续深入分析,探索滑动窗口题型一些具有模式性的解法。

    程序员小浩
  • 漫画:二叉树系列 第五讲(BST的删除)

    在两节中,我们了解了BST(二叉搜索树)的概念,并且知道了如何在BST中查找一个元素。那我们又如何在BST中去删除一个元素呢?我们将通过本节的例题进行学习!

    程序员小浩
  • 算法 | KMP字符串匹配

    Python字符串str是在Python编写程序过程中,最常见的一种基本数据类型。字符串是许多单个子串组成的序列,其主要是用来表示文本。字符串是不可变数据类型,...

    算法与编程之美
  • minfi 分析甲基化芯片数据 - 预处理篇

    在芯片分析中,使用探针的信号强度来衡量表达量,但是探针的信号强度会受到噪声的干扰,所以需要去除背景噪声。

    生信修炼手册
  • 腾讯蓝军安全通告:WebLogic远程代码执行漏洞(CVE-2020-14645)

    今日,Oracle官方发布WebLogic安全更新,其中修复了一个CVSS评分为9.8的严重漏洞(CVE-2020-14645),该漏洞通过T3协议和IIOP协...

    腾讯安全应急响应中心
  • 策略模式(Strategy)

    Java高级架构
  • 文本处理三剑客之grep

    grep:文本过滤,横向截取,(模式:pattern)工具           grep, egrep, fgrep(不支持正则表达式搜索) sed:stre...

    用户4877748
  • 如何选择Spark机器学习API

    译者注:本文简要介绍了四种经典的机器学习算法。 本文将简要介绍Spark机器学习库(Spark MLlib’s APIs)的各种机器学习算法,主要包括:统计算法...

    CSDN技术头条
  • MMD_5b_ComputationalAdvertising

    OnlineAlgorithms 与Offline算法的对比 BipartiteMatching 例子 问题描述 一般用于Online场合 贪心算法 描述 算法...

    用户1147754

扫码关注云+社区

领取腾讯云代金券