概述
這篇文章主要是總結(jié)一下字符串匹配問(wèn)題中最常用的算法阿纤。
我們的問(wèn)題是這樣的：
有一個(gè) t 字符串乍迄，可能是 'hello world'贼邓，有一個(gè) p 字符串售貌，可能是 'lo'腊嗡，現(xiàn)在希望能通過(guò)程序找出 t 字符串中是否包含 p 字符串管挟，如果包含缓熟，則返回第一個(gè)匹配上的子串的位置移稳。
1. 樸素算法
樸素算法的思想很簡(jiǎn)單犀勒，其實(shí)就是我們?nèi)粘Ｉ钪惺褂萌四X求解的思路屎飘，先拿 t 串的 第一個(gè)位置開始，與 p 串從頭開始進(jìn)行比較贾费，直到某個(gè)字符匹配不上钦购，則再?gòu)?t 串的第二個(gè)位置開始，與 p 串從頭開始比較……以此類推褂萧，直到某一次與 p 串完全匹配押桃，則返回對(duì)應(yīng)位置。
# -*- coding: UTF-8 -*-
def indexOf(t, p):
i = 0
j = 0
while i < len(t) and j < len(p):
# 每次從子串的頭開始匹配导犹，一個(gè)一個(gè)字符向后
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 算法的思路沒(méi)有那么直觀谎痢，找了很多資料才最終看明白磕昼。KMP 算法的關(guān)鍵是不對(duì) t 串比較的字符位置進(jìn)行回溯，回溯操作只針對(duì) p 串节猿，而回溯操作是根據(jù)提前計(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))
