包含:BF,BF改进版本,KMP
BF:暴力搜索
BF改:当判断匹配失败的字符串是不是与首字母相同 若不同,继续BF算法; 若相同,直接将首字母移到当前位置
KMP:通过前缀与后缀发现待匹配字符串本身的特性,匹配失败时一次性移动多个字符以减少工作量
# hstring为长字符串;substring为待匹配的字符串
def bf(hstring: str, substring: str):
hlen = len(hstring)
slen = len(substring)
if (hlen == 0) or (slen == 0) or (hlen < slen):
return None
for i in range(hlen - slen + 1): # 母串逐一字符匹配
is_find = True
for j in range(slen): # 循环子串
if hstring[i + j] != substring[j]:
is_find = False
break # 如果匹配失败,之前所做的所有匹配工作全部舍弃,转而开始母串下一个字符的重新匹配
if is_find:
return i
return False
def bf_plus(hstring: str, substring: str):
hlen = len(hstring)
slen = len(substring)
if (hlen == 0) or (slen == 0) or (hlen < slen):
return None
i = 0
while i < hlen - slen:
is_find = True
for j in range(slen): # 循环子串
ch1 = hstring[i + j]
ch2 = substring[j]
if ch1 != ch2:
is_find = False
# 当匹配失败时,检查败的字符串是不是与首字母相同,若不同,继续BF算法;若相同,直接将首字母移到当前位置
if (ch1 == substring[0]) and (j >= 1):
ipos = i + j
i = ipos - 1
break
i += 1
if is_find:
return i - 1
return False
def KMP(hstring, substring):
hlen = len(hstring)
slen = len(substring)
if (hlen == 0) or (slen == 0) or (hlen < slen):
return None
def get_move_list(string): # 根据最长前缀与最长后缀判断移动的位置
n = len(string)
temp_move_list = [0] # 只有一个字符填充为0
j = 0
for i in range(1, n):
while j > 0 and string[i] != string[j]:
j = temp_move_list[j]
if string[i] == string[j]:
j += 1
temp_move_list.append(j)
return temp_move_list
move_list = get_move_list(substring)
j = 0
for i in range(hlen):
while hstring[i] != substring[j] and j > 0:
j = move_list[j - 1] # 匹配失败,确定移动后的位置
if hstring[i] == substring[j]:
j += 1
if j == slen:
return i - slen + 1
return False