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 End
zAlgorithm(文字,图案)
输入- 要搜索的主要文本和样式
输出-找到图案的位置
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