首页 ›存档› 技术 › 查看内容

算法---查找子串

2018-3-30 13:00 |来自: 互联网 435 0

摘要: 这几天都是算法的内容，原因是部分朋友反馈，web.py的内容太枯燥了，很多人都没有跟上呢，因此，web.py搭建简易博客的系列放缓速度，增加几篇算法的文章。今天要说的是查找子串，这个方法之前在线上交流时带着大家 ...

这几天都是算法的内容，原因是部分朋友反馈，web.py的内容太枯燥了，很多人都没有跟上呢，因此，web.py搭建简易博客的系列放缓速度，增加几篇算法的文章。

今天要说的是查找子串，这个方法之前在线上交流时带着大家一起写过，今天再提出来算是温习巩固。

算法思路

找到匹配子串第一个字符的位置

在目标字符串里，首先要找到和子串第一个字符相同的字符，因为这是可能的子串开始的位置

当第一步完成后，接下来要比较剩余的部分是不是完全匹配

这一步尤为关键，虽然找到了匹配子串第一个字符的位置，但还不能确定这就是子串开始的位置，接下来要逐个比对，确定从这个位置开始，目标串的每一个字符都匹配子串对应位上的字符,这种比对关系，可以用下面的示意图来展示

明确了这两步的作用后，写出代码并不难，当然还需要注意一些边界逻辑

示例代码

#coding=utf-8
string = "I love python"
sub = 'pyth'

def find(string,sub):
  index = -1
  for i in range(len(string)):
    if string[i] == sub[0]:
      m = i
      n = 0
      while m

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除

路过

雷人

握手

鲜花

鸡蛋

收藏分享邀请

上一篇：免笔试入职|2017中兴捧月算法精英挑战赛攻略下一篇：Linux中内存buffer和cache的区别

算法---查找子串

相关分类