用python实现PM算法

PM算法是一种基于字符串匹配的算法，它的实现可以用Python语言来完成。下面是一个基本的PM算法实现：

def pm_algorithm(pattern, text):
    m, n = len(pattern), len(text)
    pat_lst = [pattern[i:j] for i in range(m) for j in range(i+1, m+1)]
    pat_len_lst = [len(pat) for pat in pat_lst]
    pat_dict = {pat_lst[i]: pat_len_lst[i] for i in range(len(pat_lst))}
    j = 0
    i = 0
    while i < n:
        if text[i:i+j+1] in pat_dict:
            if pat_dict[text[i:i+j+1]] == j+1:
                return i-j
            else:
                j += 1
        else:
            i = i - j + 1
            j = 0
    return -1

PM算法的基本思路是将模式串拆分成所有可能的子串，并将其存储在一个字典中。在匹配时，每次从文本串中取出长度为j+1的子串，判断其是否在字典中，如果在，则判断其对应的值是否等于j+1，如果相等，则说明找到了匹配的位置，否则将j增加1进行下一次匹配。如果不在字典中，则将i减去j+1，j清零并从下一个位置开始匹配。最后如果没有找到匹配，则返回-1。