用python实现PM算法
时间: 2023-11-10 08:08:44 浏览: 167
PM算法是一种基于字符串匹配的算法,它的实现可以用Python语言来完成。下面是一个基本的PM算法实现:
```python
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。
阅读全文