概述
這篇文章主要是總結(jié)一下字符串匹配問題中最常用的算法。
我們的問題是這樣的：
有一個 t 字符串，可能是 'hello world'，有一個 p 字符串，可能是 'lo'，現(xiàn)在希望能通過程序找出 t 字符串中是否包含 p 字符串，如果包含，則返回第一個匹配上的子串的位置。
1. 樸素算法
樸素算法的思想很簡單，其實就是我們?nèi)粘Ｉ钪惺褂萌四X求解的思路，先拿 t 串的 第一個位置開始，與 p 串從頭開始進行比較，直到某個字符匹配不上，則再從 t 串的第二個位置開始，與 p 串從頭開始比較……以此類推，直到某一次與 p 串完全匹配，則返回對應(yīng)位置。
# -*- coding: UTF-8 -*-
def indexOf(t, p):
i = 0
j = 0
while i < len(t) and j < len(p):
# 每次從子串的頭開始匹配，一個一個字符向后
if(t[i] == p[j]):
i = i + 1
j = j + 1
# 匹配失敗，則需要回溯 i 值
else:
i = i - j + 1
j = 0
if j == len(p):
return i - j
else:
return -1
t = 'hello world'
p = 'or'
print(indexOf(t, p))
2. KMP 算法
相比起樸素算法，KMP 算法的思路沒有那么直觀，找了很多資料才最終看明白。KMP 算法的關(guān)鍵是不對 t 串比較的字符位置進行回溯，回溯操作只針對 p 串，而回溯操作是根據(jù)提前計算好的 next 數(shù)組，其中保存了回溯的位置。
# -*- coding: UTF-8 -*-
def indexOf(t, p):
if p == None or p == '':
return -1
next = getNext(p)
i = 0
j = 0
while i < len(t) and j < len(p):
if j == -1 or t[i] == p[j]:
i += 1
j += 1
else:
j = next[j]
if j == len(p):
return i - len(p)
else:
return -1
def getNext(p):
if p == None or p == '':
return None
if len(p) == 1:
return [-1]
i = 0
j = 1
pos = 2
next = [0] * len(p)
next[0] = -1
while i < len(p) and j < len(p):
next[j] = i
if p[i] == p[j]:
i += 1
j += 1
else:
i = 0
j += 1
return next
t = 'habababzabababa'
p = 'abababzabababa'
print(indexOf(t, p))
