Z 算法
用于模式匹配的 Z 算法
Z 算法是一种线性时间的字符串匹配算法，用于模式匹配或在字符串中搜索给定模式。其目的是搜索字符串中给定模式的所有出现位置。Z 算法依赖于 Z 数组来查找模式的出现位置。Z 数组是一个整数数组，用于存储模式与文本中任意子字符串之间最长公共前缀的长度。它的长度与字符串的长度相同。
Z 算法的工作原理？
Z 算法的工作原理是构建一个名为 Z 数组的辅助数组，用于存储给定文本与文本中任意子字符串之间最长公共前缀的长度。此数组中的每个索引都存储匹配字符的数量，从第 0 个索引开始直到当前索引。
Z 算法需要以下步骤 −
首先，将模式和给定字符串合并在一起。我们还需要在其中添加一个特殊字符，该字符在任何指定的字符串中都不存在。假设我们使用美元符号 (
$) 作为特殊字符。然后，为这个新创建的字符串构建 Z 数组。
现在，检查 Z 数组的每个索引，找到其值与被搜索模式的长度匹配的位置。如果值和长度匹配，则将模式标记为已找到。
最后一步，用模式长度 + 1 减去索引号，即可得出模式的索引。
下图演示了上述方法 −
让我们了解一下输入输出场景 −
输入： 主字符串："ABAAABCDBBABCDDEBCABC" 模式："ABC" 输出： 在以下位置找到图案： 4 在以下位置找到图案： 10 在以下位置找到图案： 18
在上述场景中，我们在主字符串"ABAAAABCDBBABCDDEBCABC"中查找模式"ABC"。我们将检查主字符串中的每个位置，并记下找到匹配的位置。我们在位置 4、10 和 18 处找到了模式"ABC"。
示例
以下示例演示了各种编程语言中 Z 算法的用法。 −
#include <stdio.h>
#include <string.h>
// 填充Z数组的函数
void fillZArray(const char* conStr, int zArr[]) {
int n = strlen(conStr);
int windLeft, windRight, k;
// Initialize the window size to 0
windLeft = windRight = 0;
// 迭代新字符串的字符
for (int i = 1; i < n; i++) {
// 检查当前索引是否大于窗口的右边界
if (i > windRight) {
// 将窗口大小重置为 0 并将其定位到当前索引处
windLeft = windRight = i;
// 只要字符匹配，就扩展窗口的右边界
while (windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
windRight++;
}
// 设置当前索引的 Z 值
zArr[i] = windRight - windLeft;
// decrementing right bound
windRight--;
} else {
// 计算窗口中对应的索引
k = i - windLeft;
// 如果相应索引处的 Z 值小于剩余间隔
if (zArr[k] < windRight - i + 1) {
zArr[i] = zArr[k];
} else {
// 将窗口左边界重置为当前索引
windLeft = i;
// 只要字符匹配，就扩展窗口的右边界
while (windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
windRight++;
}
// 设置当前索引的 Z 值
zArr[i] = windRight - windLeft;
// 减少窗口的右边界
windRight--;
}
}
}
}
// 实现模式搜索的 Z 算法的函数
void zAlgorithm(const char* mainString, const char* pattern, int array[], int *index) {
// 将模式、特殊字符和主字符串连接起来
char concatedStr[strlen(mainString) + strlen(pattern) + 1];
strcpy(concatedStr, pattern);
strcat(concatedStr, "$");
strcat(concatedStr, mainString);
int patLen = strlen(pattern);
int len = strlen(concatedStr);
// 初始化Z数组
int zArr[len];
// 填充Z数组
fillZArray(concatedStr, zArr);
// 迭代 Z 数组
for (int i = 0; i < len; i++) {
// 如果 Z 值等于模式的长度，则找到模式
if (zArr[i] == patLen) {
(*index)++;
array[(*index)] = i - patLen - 1;
}
}
}
int main() {
const char* mainString = "ABAAABCDBBABCDDEBCABC";
const char* pattern = "ABC";
// 初始化位置数组和索引
int locArray[strlen(mainString)];
int index = -1;
// 调用Z算法函数
zAlgorithm(mainString, pattern, locArray, &index);
// 打印结果
for (int i = 0; i <= index; i++) {
printf("在以下位置找到图案： %d
", locArray[i]);
}
return 0;
}
输出
在以下位置找到图案： 4 在以下位置找到图案： 10 在以下位置找到图案： 18
#include<iostream>
using namespace std;
// 填充Z数组的函数
void fillZArray(string conStr, int zArr[]) {
int n = conStr.size();
int windLeft, windRight, k;
// 最初窗口大小为 0
windLeft = windRight = 0;
// 迭代新字符串的字符
for(int i = 1; i < n; i++) {
// 检查当前索引是否大于窗口的右边界
if(i > windRight) {
// 将窗口大小重置为 0 并将其定位到当前索引处
windLeft = windRight = i;
// 只要字符匹配，就扩展窗口的右边界
while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
windRight++;
}
// 设置当前索引的 Z 值
zArr[i] = windRight-windLeft;
// decrementing right bound
windRight--;
}else {
// 计算窗口中对应的索引
k = i-windLeft;
// 如果相应索引处的 Z 值小于剩余间隔
if(zArr[k] < windRight-i+1)
zArr[i] = zArr[k];
else {
// 将窗口左边界重置为当前索引
windLeft = i;
// 只要字符匹配，就扩展窗口的右边界
while(windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
windRight++;
}
// 设置当前索引的 Z 值
zArr[i] = windRight - windLeft;
// 减少窗口的右边界
windRight--;
}
}
}
}
// 实现模式搜索的 Z 算法的函数
void zAlgorithm(string mainString, string pattern, int array[], int *index) {
// 将模式、特殊字符和主字符串连接起来
string concatedStr = pattern + "$" + mainString;
int patLen = pattern.size();
int len = concatedStr.size();
// 初始化Z数组
int zArr[len];
// 填充Z数组
fillZArray(concatedStr, zArr);
// 迭代 Z 数组
for(int i = 0; i<len; i++) {
// 如果 Z 值等于模式的长度，则找到模式
if(zArr[i] == patLen) {
(*index)++;
array[(*index)] = i - patLen -1;
}
}
}
int main() {
string mainString = "ABAAABCDBBABCDDEBCABC";
string pattern = "ABC";
// 初始化位置数组和索引
int locArray[mainString.size()];
int index = -1;
// 调用Z算法函数
zAlgorithm(mainString, pattern, locArray, &index);
// 打印结果
for(int i = 0; i <= index; i++) {
cout << "在以下位置找到图案： " << locArray[i]<<endl;
}
}
输出
在以下位置找到图案： 4 在以下位置找到图案： 10 在以下位置找到图案： 18
public class ZAlgorithm {
// 填充Z数组的方法
public static void fillZArray(String conStr, int[] zArr) {
int n = conStr.length();
int windLeft, windRight, k;
// 最初窗口大小为 0
windLeft = windRight = 0;
// 迭代新字符串的字符
for (int i = 1; i < n; i++) {
// 检查当前索引是否大于窗口的右边界
if (i > windRight) {
// 将窗口大小重置为 0 并将其定位到当前索引处
windLeft = windRight = i;
while (windRight < n && conStr.charAt(windRight - windLeft) == conStr.charAt(windRight)) {
windRight++;
}
// 设置当前索引的 Z 值
zArr[i] = windRight - windLeft;
windRight--;
} else {
k = i - windLeft;
if (zArr[k] < windRight - i + 1)
zArr[i] = zArr[k];
else {
windLeft = i;
while (windRight < n && conStr.charAt(windRight - windLeft) == conStr.charAt(windRight)) {
windRight++;
}
zArr[i] = windRight - windLeft;
windRight--;
}
}
}
}
// 实现模式搜索的Z算法的方法
public static void zAlgorithm(String mainString, String pattern, int[] array) {
// 将模式、特殊字符和主字符串连接起来
String concatedStr = pattern + "$" + mainString;
int patLen = pattern.length();
int len = concatedStr.length();
// 初始化Z数组
int[] zArr = new int[len];
// 填充Z数组
fillZArray(concatedStr, zArr);
int index = -1;
// 迭代 Z 数组
for (int i = 0; i < len; i++) {
// 如果 Z 值等于模式的长度，则找到模式
if (zArr[i] == patLen) {
index++;
array[index] = i - patLen - 1;
}
}
// 打印结果s
for (int i = 0; i <= index; i++) {
System.out.println("在以下位置找到图案： " + array[i]);
}
}
public static void main(String[] args) {
String mainString = "ABAAABCDBBABCDDEBCABC";
String pattern = "ABC";
// 初始化位置数组和索引
int[] locArray = new int[mainString.length()];
// 调用Z算法方法
zAlgorithm(mainString, pattern, locArray);
}
}
输出
在以下位置找到图案： 4 在以下位置找到图案： 10 在以下位置找到图案： 18
# 填充Z数组的函数
def fillZArray(conStr, zArr):
n = len(conStr)
windLeft, windRight, k = 0, 0, 0
# 迭代新字符串的字符
for i in range(1, n):
if i > windRight:
windLeft, windRight = i, i
while windRight < n and conStr[windRight - windLeft] == conStr[windRight]:
windRight += 1
zArr[i] = windRight - windLeft
windRight -= 1
else:
k = i - windLeft
if zArr[k] < windRight - i + 1:
zArr[i] = zArr[k]
else:
windLeft = i
while windRight < n and conStr[windRight - windLeft] == conStr[windRight]:
windRight += 1
zArr[i] = windRight - windLeft
windRight -= 1
# 实现模式搜索的 Z 算法的函数
def zAlgorithm(mainString, pattern, array):
concatedStr = pattern + "$" + mainString
patLen = len(pattern)
length = len(concatedStr)
zArr = [0] * length
fillZArray(concatedStr, zArr)
index = -1
for i in range(length):
if zArr[i] == patLen:
index += 1
array[index] = i - patLen - 1
return index, array
def main():
mainString = "ABAAABCDBBABCDDEBCABC"
pattern = "ABC"
locArray = [0] * len(mainString)
index, locArray = zAlgorithm(mainString, pattern, locArray)
for i in range(index + 1):
print("在以下位置找到图案：", locArray[i])
if __name__ == "__main__":
main()
输出
在以下位置找到图案： 4 在以下位置找到图案： 10 在以下位置找到图案： 18
Z 算法的复杂度
Z 算法用于线性时间运行的模式搜索。因此，其时间复杂度为 O(m + n)，其中 n 是被搜索字符串的长度，m 是被搜索模式的长度。
