基本的字符串位置查找方法
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)
新聞熱點
疑難解答
圖片精選
