Python中的字符串查找操作方法总结

yipeiwu_com7年前Python基础

基本的字符串位置查找方法
Python 查找字符串使用 变量.find("要查找的内容"[,开始位置,结束位置]),开始位置和结束位置,表示要查找的范围,为空则表示查找所有。查找到后会返回位置,位置从0开始算,如果每找到则返回-1。

str = 'a,hello' 
print str.find('hello') # 在字符串str里查找字符串hello 
>> 2     # 输出结果 

朴素匹配算法

朴素匹配算法是对目标字符串和模板字符串的一一匹配。如果匹配得上,下标向右移一位, 否则清空并重新开始匹配。

target = 'abb aba'
pattern = 'aba'

def match(target, pattern):
  i = j = 0
  n, m = len(target), len(pattern)
  while i < n and j < m:
    # 如果字符相等则目标和模板的下标都向右移
    if target[i] == pattern[j]:
      i, j = i+1, j+1
    else:
      # 如果字符不相等则目标下标切换到不相等的下标
      # 模板下标移动到初始下标
      i = i - j + 1
      j = 0
  if j == m:
    return i - j
  return -1

把上面的加上print后打印一遍

#修改的地方
else:
  i = i -j + 1
  j = 0
  print(target[i], pattern[j], i, j)

# 打印结果
b a 1 0
b a 2 0
 a 3 0
a a 4 0

循环会一直到相等的匹配值, 这个方法效率低下,主要是在不匹配时会重新把模板字符循环一次。最多可能会出现 m * (n-m +1)次。m是模板字符的长度,n-m + 1是排除不等字符的次数。

KMP 算法

kmp是通过已知匹配的字符进行移位的算法,比如上面的abb 中跟abc比较的话 ab是已知的。

def match(target, pattern):
  i = j = 0
  n, m = len(target), len(pattern)
  while i < n and j < m:
    # 如果字符相等则目标和模板的下标都向右移
    if if j == -1 and target[i] == pattern[j]:
      i, j = i+1, j+1
    else:
      # 这里通过next 函数来判断位移个数
      i = i - j + pattern_next(pattern[:j])
      j = 0
  if j == m:
    return i - j
  return -1


def pattern_next(s):  
  prefix = [s[:i+1] for i in range(len(s)-1)]
  suffix = [s[i+1:] for i in range(len(s)-1)]
  l = list(set(prefix) & set(suffix))
  return len(l)

相关文章

django 微信网页授权认证api的步骤详解

微信网页授权认证 根据微信官方文档,网页授权需要四个步骤, - 用户同意授权-获取code - 通过code 获取网页授权access_token - 通过code 获取网页授权...

Python读写unicode文件的方法

本文实例讲述了Python读写unicode文件的方法。分享给大家供大家参考。具体实现方法如下: #coding=utf-8 import os import codecs d...

python数据类型_元组、字典常用操作方法(介绍)

元组 Python的元组与列表类似,不同之处在于元组的元素不能修改。 元组使用小括号,列表使用方括号。 元组创建很简单,只需要在括号中添加元素,并使用逗号隔开即可。 tp=(1,2,...

Python面向对象程序设计之私有属性及私有方法示例

本文实例讲述了Python面向对象程序设计之私有属性及私有方法。分享给大家供大家参考,具体如下: 如果有一个对象,当需要对其进行修改属性时,有2种方法: (1)对象名.属性名=数据---...

详解python项目实战:模拟登陆CSDN

详解python项目实战:模拟登陆CSDN

前言 今天为大家介绍一个利用Python模拟登陆CSDN的案例,虽然看起来很鸡肋,有时候确会有大用处,在这里就当做是一个案例练习吧,提高自己的代码水平,也了解Python如何做到模拟登陆...