Python中的字符串查找操作方法总结-Tutoriel Python-php.cn

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

WBOY

Libérer： 2016-07-06 13:29:49

original

2506 Les gens l'ont consulté

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

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

Copier après la connexion

朴素匹配算法

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

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

Copier après la connexion

把上面的加上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

Copier après la connexion

循环会一直到相等的匹配值, 这个方法效率低下，主要是在不匹配时会重新把模板字符循环一次。最多可能会出现 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)

Copier après la connexion

Étiquettes associées：

python 字符串查找

source：php.cn

Article précédent：Python实现快速排序算法及去重的快速排序的简单示例 Article suivant：尝试用最短的Python代码来实现服务器和代理服务器

Déclaration de ce site Web

Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Derniers articles par auteur