实现线性时间匹配的Z算法

Z算法是一种可以实现线性时间匹配的算法，通过前缀串匹配，实现快速匹配。相比于经典的KMP算法，Z算法更加易懂和易用。下面将介绍Z算法的原理以及代码演示。

Z算法原理

Z算法通过前缀串搜索，即一个字符串i位开始的前缀串与该字符串前缀串匹配的最大长度。具体步骤如下：

1. 从i1位开始，比对前缀串，使用LR限制阅读间隔。

2. L-R即从0，也就是第一位字符开始匹配。

3. 若i大于R即匹配失败，从RLi开始重新匹配。

4. 若小于，可从前面匹配信息获得相关信息。

Z算法代码演示

```python

Z_Algorithm

def getZ(str):

import numpy as np

z (len(str), dtypeint64)

n len(str)

l r 0

for i in range(1, len(str)):

if i > r:

l r i

while r

r 1

z[i] r-l

r - 1

else:

k i - l

if z[k] < r-i 1:

z[i] z[k]

else:

l i

while r < n and str[r-l] str[r]:

r 1

z[i] r - l

z[0] len(str)

return z

concat pattern and text

def search(p,t):

concat p '$' t

z getZ(concat)

for i in range(len(z)):

if z[i] len(p):

print('Pattern found at index:', i-len(p)-1)

```

以上是关于Z算法的原理和代码演示，希望能够帮助您更好地理解并应用这一线性时间匹配算法。

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。