字符串的匹配模式算法
在主字符串S中查找模式字符串T的位置的操作通常称为模式匹配，例如在”abcdefghijklmn”中查找”bcd”，结果是1。今天来讨论字符串的匹配模式的两种算法。
算法是用Python实现的，主要是懒，不想编译Java代码，有空再补上Java的代码吧。
常规算法
我也不知道这种算法叫什么名字，一般人首先想到解决这个问题的算法一般都是这个，这种算法的时间复杂度是O(m*n)，m是字符串S的长度，n为字符串T的长度。
def index(string_source, string_type, position):
""" 在主字符串string_source中查找模式字符串string_type的位置
:param string_source: 主字符串
:param string_type: 模式字符串
:param position: 从主字符串的该位置起开始查找
:return: 模式字符串在主字符串的位置
"""
i = position
j = 0
while i <= len(string_source) - 1 and j <= len(string_type) - 1:
if string_source[i] == string_type[j]:
i += 1
j += 1
else:
i = i - j + 1
j = 0
if j == len(string_type):
return i - len(string_type)
else:
return -1在上述过程中，主要是利用变量i和j来代表主字符串string_source和模式字符串string_type中当前待比较的字符的位置。算法的基本思想是：从主字符串string_source的第position个字符起和模式字符串string_type的第一个字符相比较，如若相等，则继续逐个比较后续字符；若不相等，则从主字符串的下一个字符起再重新和模式字符串的第一个字符相比较，直至完全匹配。
这种算法在处理文本是效率不错，效率能接近O(m+n)，但面向更底层的二进制时，则显得力不从心，效率骤降至O(m*n)。
例如当主字符串为”0000000000000000000000000000000000000000000000000000000000000001”，而模式字符串为”00000001”时，模式串前7位都是0，每次都要比较到第8位才能知道匹配失败，而主串前63位都是0，要重复很多次这些没必要的已知会匹配失败的匹配失败，那要怎么改进呢，看下文。
KMP算法
之前的常规算法，出现匹配失败时，需要对主字符串回溯重新比较，但接下来这种算法，不需要对主字符串进行回溯，能将复杂度降低至O(m+n)，这种算法叫做KMP算法。算法的推导过程在此就不赘述了，有兴趣的同学可以自行搜索了解，在此只说说实现过程。
def index_kmp(string_source, string_type, position):
next_list = get_next(string_type)
i = position
j = 0
while i <= len(string_source) - 1 and j <= len(string_type) - 1:
if j == -1 or string_source[i] == string_type[j]:
i += 1
j += 1
else:
j = next_list[j]
if j == len(string_type):
return i - len(string_type)
else:
return -1KMP算法是在已知模式字符串next函数值的基础上执行的，所以必须知道get_next()的实现：
def get_next(string):
i = 0
next_list = [-1]
j = -1
while i < len(string) - 1:
if j == -1 or string[i] == string[j]:
i += 1
j += 1
if string[i] == string[j]:
next_list.insert(i, next_list[j])
else:
next_list.insert(i, j)
else:
j = next_list[j]
return next_listget_next()的复杂度为O(m)，通常模式字符串的长度m比主字符串的长度n小得多，因此对于整个算法来说增加这点时间是值得的，所以整个KMP算法的实际复杂度为O(n+2m)。
小结
-
虽然常规算法的时间复杂度为O(n*m)，但是一般执行时间近似于O(n+m)
-
KMP算法最大的特点是整个匹配过程只需要对主字符串从头到尾扫描一遍，这对于处理外部输入的庞大的文件十分有效，可以边读入边匹配，对于节省内存很有帮助
除非另有声明，本博客所有文章采用的授权方式为 自由转载-非商用-非衍生-保持署名 ，转载请务必注明出处，谢谢。
