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

Python  /  管理员 发布于 7年前   119

基本的字符串位置查找方法
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 0b a 2 0 a 3 0a 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 -1def 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)

您可能感兴趣的文章:

• Python字符串的常见操作实例小结
• Python中字符串的常见操作技巧总结
• Python 字符串操作方法大全
• python中字符串的操作方法大全
• Python 字符串操作(string替换、删除、截取、复制、连接、比较、查找、包含、大小写转换、分割等)
• Python中常用操作字符串的函数与方法总结
• python字符串的常用操作方法小结
• Python对字符串实现去重操作的方法示例
• Python中的字符串替换操作示例
• Python基础之字符串常见操作经典实例详解