C Program
#include <stdio.h>
#include <string.h>
void computeZ(char *str, int Z[]) {
int n = strlen(str), L = 0, R = 0;
for (int i = 1; i < n; i++) {
if (i <= R)
Z[i] = (R - i + 1 < Z[i - L]) ? R - i + 1 : Z[i - L];
while (i + Z[i] < n && str[Z[i]] == str[i + Z[i]])
Z[i]++;
if (i + Z[i] - 1 > R) {
L = i;
R = i + Z[i] - 1;
}
}
}
void Zsearch(char *text, char *pattern) {
char concat[1000];
sprintf(concat, "%s$%s", pattern, text);
int l = strlen(concat);
int Z[l];
for (int i = 0; i < l; i++) Z[i] = 0;
computeZ(concat, Z);
for (int i = 0; i < l; i++) {
if (Z[i] == strlen(pattern))
printf("Pattern found at index %d\n", i - strlen(pattern) - 1);
}
}
int main() {
char text[] = "ababcababcabc";
char pattern[] = "abc";
Zsearch(text, pattern);
return 0;
}C Output
Pattern found at index 2 Pattern found at index 7 Pattern found at index 9
C++ Program
#include <bits/stdc++.h>
using namespace std;
void computeZ(string str, vector<int> &Z) {
int n = str.size(), L = 0, R = 0;
for (int i = 1; i < n; i++) {
if (i <= R)
Z[i] = min(R - i + 1, Z[i - L]);
while (i + Z[i] < n && str[Z[i]] == str[i + Z[i]])
Z[i]++;
if (i + Z[i] - 1 > R) {
L = i;
R = i + Z[i] - 1;
}
}
}
void Zsearch(string text, string pattern) {
string concat = pattern + "$" + text;
int l = concat.size();
vector<int> Z(l, 0);
computeZ(concat, Z);
for (int i = 0; i < l; i++) {
if (Z[i] == pattern.size())
cout << "Pattern found at index " << i - pattern.size() - 1 << endl;
}
}
int main() {
string text = "ababcababcabc";
string pattern = "abc";
Zsearch(text, pattern);
return 0;
}C++ Output
Pattern found at index 2 Pattern found at index 7 Pattern found at index 9
JAVA Program
public class ZAlgorithm {
public static void computeZ(String str, int Z[]) {
int n = str.length(), L = 0, R = 0;
for (int i = 1; i < n; i++) {
if (i <= R)
Z[i] = Math.min(R - i + 1, Z[i - L]);
while (i + Z[i] < n && str.charAt(Z[i]) == str.charAt(i + Z[i]))
Z[i]++;
if (i + Z[i] - 1 > R) {
L = i;
R = i + Z[i] - 1;
}
}
}
public static void Zsearch(String text, String pattern) {
String concat = pattern + "$" + text;
int l = concat.length();
int Z[] = new int[l];
computeZ(concat, Z);
for (int i = 0; i < l; i++) {
if (Z[i] == pattern.length())
System.out.println("Pattern found at index " + (i - pattern.length() - 1));
}
}
public static void main(String[] args) {
String text = "ababcababcabc";
String pattern = "abc";
Zsearch(text, pattern);
}
}JAVA Output
Pattern found at index 2 Pattern found at index 7 Pattern found at index 9
Python Program
def computeZ(s):
n = len(s)
Z = [0] * n
L, R = 0, 0
for i in range(1, n):
if i <= R:
Z[i] = min(R - i + 1, Z[i - L])
while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:
Z[i] += 1
if i + Z[i] - 1 > R:
L, R = i, i + Z[i] - 1
return Z
def Zsearch(text, pattern):
concat = pattern + "$" + text
Z = computeZ(concat)
for i in range(len(Z)):
if Z[i] == len(pattern):
print("Pattern found at index", i - len(pattern) - 1)
text = "ababcababcabc"
pattern = "abc"
Zsearch(text, pattern)Python Output
Pattern found at index 2 Pattern found at index 7 Pattern found at index 9
In-Depth Explanation
Example
Suppose you are reading a large book and want to search for the word "magic" within it. You can go from word to word and continue verifying, but that would be time-consuming. Rather, if you already know how the pattern "magic" looks like and can easily bypass unnecessary verifications, you would be quicker. This is precisely what the Z-Algorithm accomplishes—it preprocesses the text and pattern so that it doesn't perform redundant comparisons, resulting in a quicker search.
Real-Life Analogy
Imagine searching for something in a search bar of your mobile phone. As you enter "ab" into the search bar, the phone immediately shows all words beginning with "ab" within your chat history or notes. The phone is not actually re-searching each word from the very beginning—it employs optimized algorithms such as Z-Algorithm or KMP to rapidly identify matches. This analogy demonstrates how critical efficient pattern matching is for our everyday digital experiences.
Why It Matters
The Z-Algorithm is important in that it answers the pattern matching problem in linear time of O(n+m), where n is the length of the text and m is the length of the pattern. Unlike the naive method of possibly quadratic time, this efficiency is of the utmost importance when dealing with large data such as DNA sequences, log analysis, spam filtering, or search engines.
Learning Insights
When novices study Z-Algorithm, they realize how preprocessing saves us from high time complexity. It illustrates the necessity of employing additional space (Z array) to make it efficient. It also instructs how the management of a "window" (L, R pointers) facilitates reuse of earlier computed values. This technique of reuse of past computations is extensively utilized in dynamic programming and sophisticated algorithm design.
Interview Relevance
Pattern matching problems such as Z-Algorithm implementation, KMP, or Rabin-Karp are quite frequent in code interviews for Google, Amazon, Microsoft, and Adobe. The ability to implement Z-Algorithm from ground up indicates excellent command over string manipulation, optimization, and algorithmic thinking. It also indicates that the candidate possesses the capability to deal with practical problems related to search and text analysis at an efficient level.
Real-World Use Cases
Search Engines employ string matching variants to index and retrieve web pages.
Plagiarism Detection Tools match documents to identify duplicated text sections.
DNA Sequence Analysis employs rapid pattern matching to identify genetic markers.
Spam Filters match keywords to identify unwanted messages.
SEO-Optimized Conclusion
The Z-Algorithm for pattern matching is amongst the most powerful linear-time string searching algorithms in computer science. It not only makes you ready for coding interviews but also aids in solving actual problems like DNA sequencing, text searching, and spam filtering effectively. With minimal examples and efficient code in C, C++, Java, and Python, this description simplifies the learning of the idea of efficient string matching even for beginners. Learning the Z-Algorithm provides a solid algorithmic foundation and helps you gain an advantage in both competitive programming contests and academic exams.
Social Plugin