【数据结构与算法】什么是串?什么是KMP算法?字符串匹配是什么?
发布日期:2021-06-29 15:36:08
浏览次数:2
分类:技术文章
本文共 1292 字,大约阅读时间需要 4 分钟。
串(Sequence)
串就是开发中非常熟悉的字符串,是由若干个字符组成的有限序列。
串匹配算法
本节主要研究串的匹配问题,比如:
查找一个模式串(pattern)在文本串(text)中的位置
几个经典的串匹配算法
- 暴力算法
- KMP算法
1.暴力算法
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = “hello”, needle = “ll”
输出: 2 示例 2:输入: haystack = “aaaaa”, needle = “bba”
输出: -1class Solution { public int strStr(String haystack, String needle) { char[] s1 = haystack.toCharArray(); char[] s2 = needle.toCharArray(); int len1 = s1.length; int len2 = s2.length; if(len2==0&&len1==0){ return 0; } // 选定其开始 int i,j; for(i=0;i<=len1-len2;i++){ for(j=0;j
2.KMP算法
KMP 算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,效率很高,但是确实有点复杂。
先在开头约定,本文用 pat 表示模式串,长度为 M,txt 表示文本串,长度为 N。KMP 算法是在 txt 中查找子串 pat,如果存在,返回这个子串的起始索引,否则返回 -1。
KMP 算法应该是,一波诡异的操作处理 pat 后形成一个一维的数组 next,然后根据这个数组经过又一波复杂操作去匹配 txt。时间复杂度 O(N),空间复杂度 O(M)。其实它这个 next 数组就相当于 dp 数组,其中元素的含义跟 pat 的前缀和后缀有关,判定规则比较复杂,不好理解。本文则用一个二维的 dp 数组(但空间复杂度还是 O(M)),重新定义其中元素的含义,使得代码长度大大减少,可解释性大大提高。
class Solution { public int strStr(String haystack, String needle) { int len1 = haystack.length(); int len2 = needle.length(); if(len1==0&&len2==0){ return 0; } if(len1
转载地址:https://codingchaozhang.blog.csdn.net/article/details/115430559 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月23日 16时31分34秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
spark: rdd的应用(scala api)
2019-04-29
spark: rdd的应用(java api)
2019-04-29
yarn: 资源调度机制
2019-04-29
spark的shell脚本分析
2019-04-29
推荐算法: 基于用户的协同过滤算法
2019-04-29
推荐算法:基于物品的协同过滤算法
2019-04-29
docker系列3:docker搭建CDH集群[单机单节点]
2019-04-29
ubuntu 16:使用系统自带的中文输入法
2019-04-29
k8s单机版[ microk8s ]
2019-04-29
docker系列6 :k8s集群[ 解压安装 ]
2019-04-29
maven- idea: 打包可执行jar
2019-04-29
docker系列2: windows安装docker
2019-04-29
hbase数据转移: 导入导出
2019-04-29
docker系列7: docker搭建mysql
2019-04-29
windows server 2012设置远程连接断开后自动注销
2019-04-29
python基础:list,map,open()文件读写
2019-04-29
Go面向对象-接口
2019-04-29
Go-多路选择和超时控制
2019-04-29
Go-channel的关闭和广播
2019-04-29
Go-任务的取消
2019-04-29