字符串匹配之KMP算法

思想

朴素的字符串匹配算法是从前到后连续的一个字符一个字符的比较判断是否一致，其时间复杂度为O(mn)，其中m为匹配模式的字符串长度，而n为待匹配的字符串长度。

KMP算法欲改进的就是在匹配时连续一个一个匹配会有做无用功的时候，可以跳过一些字符再比较。而可以跳过的字符通过计算匹配模式字符串的哪些前缀和后缀相同可得。

时间复杂度可以降为线性的O(m+n)。

代码实现

#####################
#
# KMP Algorithm
#
#####################

def kmp_string_search(s, p):
    """
    :param s:string
    :param p:string, pattern
    :return:list
    """
    # build pattern string array
    m = len(p) 
    li = [0] * (m+1)
    i = 0
    for j in range(1, m):
        while i > 0 and p[j] != p[i]:
            i = li[i]

        # 当有j+1个字符的时候，有i+1个前后缀重叠
        if p[j] == p[i]:
            i += 1
            li[j+1] = i + 1

    # use above array to search 
    n = len(s)
    i = 0
    finds = []
    for j in range(0, n):
        while i > 0 and s[j] != p[i]:
            i = li[i]
        
        if s[j] == p[i]:
            if i == m-1:
                finds.append(j-m+1)
                i = li[i+1]
            else:
                i += 1
    return finds

if __name__ == "__main__":
    s = 'bacbababaabcbababacababacababacababacb'
    p = 'ababacab'
    print(s)
    print(p)
    finds = kmp_string_search(s, p)
    for index in finds:
        print('-'*len(s))
        print(s)
        print('%s%s' % (' '*index, p))