Sunday 匹配是啥?
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算法,我们从头部开始比较,一旦发现不匹配,直接找到主串中位于模式串后面的第一个字符,即下面绿色的 “s”。(这里说明一下,为什么是找模式串后面的第一个字符。在把模式串和目标串对齐后,如果发现不匹配,那肯定需要移动模式串。问题是需要移动多少步。各字符串匹配算法之间的差别也来自于这个地方,对于KMP,是建立部分匹配表来计算。BM,是反向比较计算移动量。对于SUNDAY,就是找到模式串后的第一个字符。因为,无论模式串移动多少步,模式串后的第一个字符都要参与下一次比较,也就是这里的 “s”)
找到了模式串后的第一个字符 “s”,接下来该怎么做?我们需要查看模式串中是否包含这个元素,如果不包含那就可以跳过一大片,从该字符的下一个字符开始比较。
因为仍然不匹配(空格和l),我们继续重复上面的过程。找到模式串的下一个元素:
现在有意思了,我们发现 t 被包含于模式串中,并且 t 出现在模式串倒数第3个。所以我们把模式串向前移动3个单位:
有内味了,我们发现竟然匹配成功了,是不是很神奇?证明的过程今天暂且不谈(后面我会出一个算法证明篇,来证明之前讲过的一些算法。我需要你做的是,掌握上面这些!)
捞干货,这个过程里我们做了一些什么:
- 对齐目标串和模式串,从前向后匹配
- 关注主串中位于模式串后面的第一个元素(核心)
- 如果关注的字符没有在子串中出现则直接跳过
- 否则开始移动模式串,移动位数 = 子串长度 - 该字符最右出现的位置(以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 匹配是啥?相关教程
-
基于词向量word2vec匹配的英文问答系统
基于词向量word2vec匹配的英文问答系统 环境准备 python3.6pandas --读取并处理csv文件nltk --http://www.nltk.org/ 自然语言处理工具包,用于分词,词干提取,语料库gensim -- 训练word2vec词向量的工具包 实现过程 导入工具包 import pandas as pd from nlt
-
MATLAB图像处理之直方图匹配(图像合理增强)
MATLAB图像处理之直方图匹配(图像合理增强) 先拿结果来看,第一幅是原图 第二幅是直方图均衡化后的图像增强 第三幅是直方图匹配后的处理结果 第二幅 第三幅来看 直接均衡化 会大大增加对比对 但是 有时不符合美观 %直方图匹配 %直方图均衡有时并不能总取得
-
OpenCV-Python官方教程-16-模板匹配
OpenCV-Python官方教程-16-模板匹配 模板匹配是用来在一副大图中搜寻查找模版图像位置的方法。OpenCV 为我们提供了函数:cv2.matchTemplate()。和 2D 卷积一样,它也是用模板图像在输入图像(大图)上滑动,并在每一个位置对模板图像和与其对应的输入图像的子
-
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
-
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
-
【算法拾遗·字符串篇】KMP字符串匹配算法
【算法拾遗·字符串篇】KMP字符串匹配算法 KMP字符串匹配算法 问题描述 暴力搜索匹配 KMP匹配 图解: 1、构建最长公共前后缀表 2、KMP匹配操作 总结: 代码: 问题描述 已知字符串 text 和 字符串 pattern, 问 pattern 是否为 text 的子串 暴力搜索匹配 int m
-
字符串模式匹配(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;
-
php 正则匹配中文 乱码问题
php正则匹配中文乱码的解决办法:首先打开PHP代码文件;然后在代码文件中加上UTF8修饰符即可,其正则表达式的语句如“preg_replace(/[万]/u,萬,$a);”。 推荐:《PHP视频教程》 具体问题: PHP字符串中用正则表达式匹配中文出现乱码 ?phpecho h2正则表达式匹