概述
这篇文章主要是总结一下字符串匹配问题中最常用的算法。
我们的问题是这样的：
有一个 t 字符串，可能是 'hello world'，有一个 p 字符串，可能是 'lo'，现在希望能通过程序找出 t 字符串中是否包含 p 字符串，如果包含，则返回第一个匹配上的子串的位置。
1. 朴素算法
朴素算法的思想很简单，其实就是我们日常生活中使用人脑求解的思路，先拿 t 串的 第一个位置开始，与 p 串从头开始进行比较，直到某个字符匹配不上，则再从 t 串的第二个位置开始，与 p 串从头开始比较……以此类推，直到某一次与 p 串完全匹配，则返回对应位置。
# -*- 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 算法的关键是不对 t 串比较的字符位置进行回溯，回溯操作只针对 p 串，而回溯操作是根据提前计算好的 next 数组，其中保存了回溯的位置。
# -*- 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))
