本系列为数据结构学习笔记(待汇总)。

1 朴素的模式匹配算法

对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做子串的长度的小循环，直到匹配成功或全部遍历完成为止。

Python实现：

def index(S,T):
    if len(T)>len(S):
        return False
    i, j = 0, 0
    while i <len(S) and j < len(T):
            if S[i] == T[j]:
                i += 1
                j += 1
            else:
                i = i-j+1
                j = 0
    if j == len(T):
        return i-len(T)
    else:
        return False
if __name__ == '__main__':
    result = index('goodgoogle','google')
    print(result)

时间复杂度：

最坏情况：一开始就匹配成功，时间复杂度为$O(1)$；
稍差一些：如果每次都是首字母就不匹配，那么对子串的循环就不必进行了，时间复杂度为$O(n+m)$，其中 n 为主串长度， m 为要匹配的子串长度；
平均情况：根据等概率原则，平均是 $(n+m) /2$ 次查找，时间复杂度为 $O(n+m)$；
最差情况：每次不成功的匹配都发生在子串的最后一个字符，时间复杂度为 $O((n- m+ 1)*m)$。

2 KMP模式匹配算法

通过对模式串(子串)的一个预处理，将时间复杂度减少到了一个线性的水平。

举例：首先我们有主串：acabaabaabcacaabc，有模式串：abaabcac，现在假设我们匹配到了如下的图的步骤：

现在模式串的第六个字符和主串匹配不上了，那么现在我们就需要把模式串往右移动，并且重新选择主串和模式串的比较位置重新开始比较。

朴素模式匹配的做法是直接把子串向右移动一位，然后，主串的第四个字符和我们模式串的第一个字符重新开始做比较。
但是其实主串的第三个字符到第六个字符我们都是已经和模式串做过比较的，而且我们知道他们的各个位置上的内容是什么，那么为什么不把这些已经知道的信息充分利用起来了？比如：我们知道模式串中红色的两个字符和绿色的两个字符是相等的，而且红色的两个字符正好是模式串开始的两个字符，所以我们可以直接把模式串向右移动四位，然后，我们主串从刚才发现不匹配那个字符位置开始和模式串的第三个位置比较，这样我们就可以减少五次比较。

这个时候，我们就需要对我们的模式串做一个预处理，通过预处理我们可得到一个next数组，它保存的就是当我们在模式串某个位置匹配失败后，应该从模式串的哪个位置重新开始比较。

mark

def get_next(T): #KMP
    next = [0]
    i = 1
    j = 0
    while i < len(T):
        if j == 0 or T[j-1] == T[i-1]:
            i += 1
            j += 1
            next.append(j)
        else:
            j = next[j-1]
    return next

def index(S,T):
    if len(T)>len(S):
        return False
    next = get_next(T)
    i, j = 0, 0
    while i <len(S) and j < len(T):
            if j == 0 or S[i] == T[j]:
                i += 1
                j += 1
            else:
                j = next[j-1]
    if j == len(T):
        return i-len(T)
    else:
        return False

if __name__ == '__main__':
    next = get_next('ababaaaba')
    print(next)
    result = index('ababaabc','abc')
    print(result)

改进的KMP模式匹配算法
如果模式串中的当前位置的字符与前缀字符相等，则将该前缀字符的next值赋给当前next值。

def get_nextval(T):#改进的KMP
    nextval = [0]
    i = 1
    j = 0
    while i < len(T):
        if j == 0 or T[j-1] == T[i-1]:
            i += 1
            j += 1
            if T[j-1] != T[i-1]:
                nextval.append(j)
            else:
                nextval.append(nextval[j-1])
        else:
            j = nextval[j-1]
    return nextval

参考文献：
程杰. 大话数据结构