Python中的字符串查找操作方法總結(jié)

更新時間：2016年06月27日 15:40:14 作者：mink的小屋

這里我們來整理一下Python中的字符串查找操作方法總結(jié),除了基本的find()方法外,還會講解到樸素匹配算法和KMP算法的使用:

基本的字符串位置查找方法
Python 查找字符串使用變量.find("要查找的內(nèi)容"[，開始位置，結(jié)束位置])，開始位置和結(jié)束位置，表示要查找的范圍，為空則表示查找所有。查找到后會返回位置，位置從0開始算，如果每找到則返回-1。

str = 'a,hello' 
print str.find('hello') # 在字符串str里查找字符串hello 
>> 2     # 輸出結(jié)果

樸素匹配算法

樸素匹配算法是對目標(biāo)字符串和模板字符串的一一匹配。如果匹配得上,下標(biāo)向右移一位, 否則清空并重新開始匹配。

target = 'abb aba'
pattern = 'aba'

def match(target, pattern):
  i = j = 0
  n, m = len(target), len(pattern)
  while i < n and j < m:
    # 如果字符相等則目標(biāo)和模板的下標(biāo)都向右移
    if target[i] == pattern[j]:
      i, j = i+1, j+1
    else:
      # 如果字符不相等則目標(biāo)下標(biāo)切換到不相等的下標(biāo)
      # 模板下標(biāo)移動到初始下標(biāo)
      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)

# 打印結(jié)果
b a 1 0
b a 2 0
 a 3 0
a a 4 0

循環(huán)會一直到相等的匹配值, 這個方法效率低下，主要是在不匹配時會重新把模板字符循環(huán)一次。最多可能會出現(xiàn) m * (n-m +1)次。m是模板字符的長度，n-m + 1是排除不等字符的次數(shù)。

KMP 算法

kmp是通過已知匹配的字符進行移位的算法，比如上面的abb 中跟abc比較的話 ab是已知的。

def match(target, pattern):
  i = j = 0
  n, m = len(target), len(pattern)
  while i < n and j < m:
    # 如果字符相等則目標(biāo)和模板的下標(biāo)都向右移
    if if j == -1 and target[i] == pattern[j]:
      i, j = i+1, j+1
    else:
      # 這里通過next 函數(shù)來判斷位移個數(shù)
      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)

您可能感興趣的文章: