3

自从 4 天以来，我一直在阅读有关字符串和一些用于模式匹配的算法，为此我得到了 KMP 搜索算法，这很好，但我也知道还有另一种字符串匹配方法，它在空间和时间复杂度上与 KMP 相同，但有一个简单的解决方案。

该算法是Z-算法。

所以为此我搜索了谷歌，但我没有找到一个很好的算法解释。您能解释一下如何创建模式数组以及如何应用搜索程序吗？如果您将提供 C++ 代码，那就太好了。

4

2 回答 2

8

很长一段时间后，我明白了如何构建 Z 数组。我会在这里用简单的话来解释。

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

例子 ：

  1. 在单词 apple 中，前缀可以是 apple (or) appl (or) app (or) ap (or) a。

  2. 在单词banana中，前缀可以是banana (or) banan (or) bana (or) ban (or) ba (or) 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 个位置开始。

湾。子字符串应该是最大长度，这也是一个前缀

  1. 在索引 0 处：

从 i(0th index) 到 end 查找子字符串，这也是给定文本的前缀。

aab $ baabaa => 长度为 10 是最长的子字符串，也是文本的前缀。但这对模式匹配没有帮助，所以我们将其设置为 Z 数组中的 x。

  1. 在索引 1：

查找从位置 1 到结尾的最长子字符串，这也是文本的前缀。

这样的子字符串是：

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

湾。"a b" => 不是前缀

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

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

e. "ab $ b a" => 不是前缀

所以...

这里唯一最长的也是前缀的子字符串是“a”，它的长度是1。它存储在Z数组中。

  1. 在索引 2：

子串是：

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

湾。"b $" => 不是前缀

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

所以...

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

  1. 在索引 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”。所以我们将 3 存储在 Z 数组的索引 5 处。

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

于 2015-08-17T16:56:12.093 回答
1

在 Z-algo 中，我们构造了一个 Z 数组。

什么是 Z 阵列？对于字符串 str[0..n-1]，Z 数组的长度与字符串相同。Z 数组的元素 Z[i] 存储从 str[i] 开始的最长子串的长度，它也是 str[0..n-1] 的前缀。Z 数组的第一个条目意义较小，因为完整的字符串始终是其自身的前缀。

> Example: Index            0   1   2   3   4   5   6   7   8   9  10  11
> Text                      a   a   b   c   a   a   b   x   a   a   a   z   
> values         X          1   0   0   3   1   0   0   2   2   1   0  More
> Examples: str  = "aaaaaa" Z[]  = {x, 5, 4, 3, 2, 1}
> 
> str = "aabaacd" Z[] = {x, 1, 0, 2, 1, 0, 0}
> 
> str = "abababab" Z[] = {x, 0, 6, 0, 4, 0, 2, 0}

这个想法是连接模式和文本，并创建一个字符串“P$T”，其中 P 是模式，$ 是一个特殊字符，不应出现在模式和文本中，T 是文本。为连接字符串构建 Z 数组。在 Z 数组中，如果任意点的 Z 值等于图案长度，则图案存在于该点。

Example:
Pattern P = "aab",  Text T = "baabaa"

The concatenated string is = "aab$baabaa"

Z array for above concatenated string is {x, 1, 0, 0, 0, 
                                          3, 1, 0, 2, 1}.
Since length of pattern is 3, the value 3 in Z array 
indicates presence of pattern.

详细的解释和实现你可以在 这里找到

于 2015-08-06T21:10:10.283 回答