z算法的实现

Question

从4天开始,我正在阅读关于字符串和一些算法的模式匹配,为此我得到了KMP搜索算法,这很好,但我还得到了另一种字符串匹配方法,它与空间和时间复杂度方面的KMP相同,但有一个简单的解决方案.

算法是Z算法.

所以为此,我搜索谷歌,但我没有找到一个很好的解释算法.你能解释一下如何创建模式数组以及如何应用搜索过程吗？如果你将用c ++提供代码,这将是很好的.

Answer 1

很长一段时间后,我明白了如何构建Z数组.我会用简单的话来解释.

让我们先了解什么是前缀:

示例:

1. 在单词apple中,前缀可以是apple(或)appl(或)app(或)ap(或)a.

2. 在单词banana中,前缀可以是banana(或)banan(或)bana(或)ban(或)ba(或)b.

说明:从字符串T的开头到字符串T的结尾或结束之前匹配的字符串T的任何子字符串S都被称为前缀.

希望你明白这里的前缀是什么.

让我们看看如何构建Z数组.

让我们举个例子:aab $ baabaa

指数:0 1 2 3 4 5 6 7 8 9

文字:aab $ baabaa

Z值:x 1 0 0 0 3 1 0 2 1

注意:

一个.子串应该从第i个位置开始.

湾 substring应该是最大长度,也是前缀

1. 在索引0:

查找从i(第0个索引)到结束的子字符串,它也是给定文本的前缀.

长度为10的aab $ baabaa =>是最长的子字符串,也是文本的前缀.但是这对模式匹配没有帮助,所以我们把它作为Z数组中的x.

2. 在索引1:

查找从位置1到结尾的最长子串,它也是文本的前缀.

这样的子串是:

一个.文本"aab $ baaba a"的"a"=>前缀,长度为1.

湾 "a b"=>不是前缀

C."ab $"=>不是前缀

d."ab $ b"=>不是前缀

即 "ab $ b a"=>不是前缀

所以...

这里唯一最长的子串也是前缀是"a",其长度是1.它存储在Z数组中.

3. 在索引2:

子串是:

一个."b"=>不是前缀

湾 "b $"=>不是前缀

C."b $ b"=>不是前缀

所以...

这里没有子串,它也是文本T的前缀.所以我们在Z数组的索引2处存储零.

4. 在索引5:

子串是:

一个."a"=>文本前缀"aab $ baaba a",长度为1.

湾 "a a"=>文本前缀"aab $ baaba a",长度为2.

C."aa b"=>文本前缀"aab $ baaba a",长度为3.

d."aab a"=>不是前缀

所以...

这里最长的子串也是文本T的前缀是长度为3的"aa b".因此我们在Z数组中将索引5存储3.

最后,如果Z数组中的任何值与模式的长度相同,则该模式存在于文本T中.