您当前的位置: 首页 >  算法

暂无认证

  • 0浏览

    0关注

    92582博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

算法 | KMP字符串匹配

发布时间:2019-09-14 19:34:33 ,浏览量:0

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

1. 问题描述

Python字符串str是在Python编写程序过程中,最常见的一种基本数据类型。字符串是许多单个子串组成的序列,其主要是用来表示文本。字符串是不可变数据类型,也就是说你要改变原字符串内的元素,只能是新建另一个字符串。字符串匹配就是基于最简单的字符比较,其中的模式串就是普通字符串,所做匹配是在目标串里查找等于模式串的子串。也就是说,比较的一方是表示模式的字符串,另一方是目标字符串的所有可能子串。我们常用的就是朴素的串匹配算法和无回溯串匹配算法(KMP算法)。

2. 问题分析

字符串匹配问题可以归纳为如下的问题:在长度为n的文本T[1...n]中,查找一个长度为m的模式P[1...m]。并且假设T,P中的元素都来自一个有限字母集合Ʃ。如果存在位移s,其中0≤s≤n-m,使得T[s+1..s+m]= P[1..m]。则可以认为模式P在T中出现过。

(1) 朴素的串匹配算法

最简单的朴素匹配算法采用最直观可行的策略: (1)从左到右

关注
打赏
1653961664
查看更多评论
立即登录/注册

微信扫码登录

0.3610s