Z算法
该算法被称为Z算法，因为在此算法中，我们需要创建一个Z数组。Z数组的大小与文本大小相同。此数组用于存储从主字符串的当前字符开始的最长子字符串的长度。首先，将模式和主要文本与文本和模式中不存在的特殊符号连接起来。如果P是模式并且T是主要文本，那么在串联后，它将是P$T（假定P和T中不存在$）。
对于此算法，时间复杂度为O（m+n），因为m是模式的长度，n是主字符串的长度。
输入输出
Input: Main String: “ABAAABCDBBABCDDEBCABC”, Pattern: “ABC” Output: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
算法
fillZArray(conStr,ZArray)
输入 -conStr是pattern和主要文本的串联字符串。ZArray存储可能的最长子字符串的索引。
输出- 填充的ZArray
Begin
n := length of conStr
windLeft := 0 and windRight := 0
for i := 1 to n, do
if i > windRight, then
windLeft := i and windRight := i
while windRight < n AND conStr[windRight-windLeft] =
conStr[windRight], do
increase windRight by 1
done
ZArray[i] := windRight – windLeft
decrease windRight by 1
else
k := i – windLeft
if ZArray[k] < windRight – i +1, then
ZArray[i] := ZArray[k]
else
windLeft := i
while windRight < n AND conStr[windRight-windLeft] =
conStr[windRight], do
increase windRight by 1
done
ZArray[i] := windRight – windLeft
decrease windRight by 1
done
EndzAlgorithm（文字，图案）
输入- 要搜索的主要文本和样式
输出-找到图案的位置
Begin
conStr = concatenate pattern + “$” + text
patLen := length of pattern
len := conStr length
fillZArray(conStr, ZArray)
for i := 0 to len – 1, do
if ZArray[i] = patLen, then
print the location i – patLen – 1
done
End示例
#include<iostream>
using namespace std;
void fillZArray(string conStr, int zArr[]) {
int n = conStr.size();
int windLeft, windRight, k;
windLeft = windRight = 0; //initially window size is 0
for(int i = 1; i < n; i++) {
if(i > windRight) {
windLeft = windRight = i; //window size is 0 but position to i
while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
windRight++; //extend the right bound of window
}
zArr[i] = windRight-windLeft;
windRight--;
}else {
k = i-windLeft;
if(zArr[k] < windRight-i+1)
zArr[i] = zArr[k]; //when kth item less than remaining interval
else {
windLeft = i;
while(windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
windRight++;
}
zArr[i] = windRight - windLeft;
windRight--;
}
}
}
}
void zAlgorithm(string mainString, string pattern, int array[], int *index) {
string concatedStr = pattern + "$" + mainString; //concat with special character
int patLen = pattern.size();
int len = concatedStr.size();
int zArr[len];
fillZArray(concatedStr, zArr);
for(int i = 0; i<len; i++) {
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;
zAlgorithm(mainString, pattern, locArray, &index);
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}输出结果
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18