Z-Algorithm (Z-Function) Code Implementations
Complete Z-Algorithm (Z-Function) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Z-Algorithm (Z-Function) Guide · Launch Interactive Visualizer
C++ Implementation
// Z-Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <chrono>
class ZAlgorithm {
public:
// Compute Z-array for a given string
static std::vector<int> computeZArray(const std::string& str) {
int n = str.length();
std::vector<int> z(n, 0);
// Z[0] is the length of the string itself
z[0] = n;
int left = 0, right = 0;
for (int i = 1; i < n; i++) {
if (i > right) {
// No Z-box found yet, expand from current position
left = right = i;
while (right < n && str[right - left] == str[right]) {
right++;
}
z[i] = right - left;
right--;
} else {
// We are inside a Z-box
int k = i - left;
if (z[k] < right - i + 1) {
// Z[k] is less than remaining length, copy it
z[i] = z[k];
} else {
// Z[k] is greater than or equal to remaining length, expand
left = i;
while (right < n && str[right - left] == str[right]) {
right++;
}
z[i] = right - left;
right--;
}
}
}
return z;
}
// Z-Algorithm for pattern matching
static std::vector<int> zAlgorithmSearch(const std::string& text, const std::string& pattern) {
std::string combined = pattern + "
Loading AntInLoop...
quot; + text;
std::vector<int> z = computeZArray(combined);
std::vector<int> matches;
int patternLength = pattern.length();
for (int i = patternLength + 1; i < z.size(); i++) {
if (z[i] == patternLength) {
matches.push_back(i - patternLength - 1);
}
}
return matches;
}
// Z-Algorithm for finding all occurrences
static std::vector<int> zAlgorithmFindAll(const std::string& text, const std::string& pattern) {
return zAlgorithmSearch(text, pattern);
}
// Z-Algorithm for first occurrence
static int zAlgorithmFirstMatch(const std::string& text, const std::string& pattern) {
std::vector<int> matches = zAlgorithmSearch(text, pattern);
return matches.empty() ? -1 : matches[0];
}
// Z-Algorithm for last occurrence
static int zAlgorithmLastMatch(const std::string& text, const std::string& pattern) {
std::vector<int> matches = zAlgorithmSearch(text, pattern);
return matches.empty() ? -1 : matches[matches.size() - 1];
}
// Z-Algorithm for count only
static int zAlgorithmCount(const std::string& text, const std::string& pattern) {
return zAlgorithmSearch(text, pattern).size();
}
// Z-Algorithm with case-insensitive search
static std::vector<int> zAlgorithmCaseInsensitive(std::string text, std::string pattern) {
// Convert to lowercase
std::transform(text.begin(), text.end(), text.begin(), ::tolower);
std::transform(pattern.begin(), pattern.end(), pattern.begin(), ::tolower);
return zAlgorithmSearch(text, pattern);
}
// Z-Algorithm for multiple patterns
static std::unordered_map<std::string, std::vector<int>> zAlgorithmMultiplePatterns(
const std::string& text, const std::vector<std::string>& patterns) {
std::unordered_map<std::string, std::vector<int>> results;
for (const auto& pattern : patterns) {
results[pattern] = zAlgorithmSearch(text, pattern);
}
return results;
}
// Z-Algorithm for finding longest common prefix
static int zAlgorithmLongestCommonPrefix(const std::string& str1, const std::string& str2) {
std::string combined = str1 + "
Loading AntInLoop...
quot; + str2;
std::vector<int> z = computeZArray(combined);
// Find the maximum Z value after the separator
int maxZ = 0;
for (int i = str1.length() + 1; i < z.size(); i++) {
maxZ = std::max(maxZ, z[i]);
}
return maxZ;
}
// Z-Algorithm for finding all palindromes
static std::vector<std::string> zAlgorithmFindPalindromes(const std::string& str) {
std::vector<std::string> palindromes;
int n = str.length();
for (int i = 0; i < n; i++) {
// Check odd length palindromes
std::string oddPalindrome = expandPalindrome(str, i, i);
if (oddPalindrome.length() > 1) {
palindromes.push_back(oddPalindrome);
}
// Check even length palindromes
if (i < n - 1) {
std::string evenPalindrome = expandPalindrome(str, i, i + 1);
if (evenPalindrome.length() > 1) {
palindromes.push_back(evenPalindrome);
}
}
}
return palindromes;
}
private:
static std::string expandPalindrome(const std::string& str, int left, int right) {
while (left >= 0 && right < str.length() && str[left] == str[right]) {
left--;
right++;
}
return str.substr(left + 1, right - left - 1);
}
public:
// Z-Algorithm for finding repeated patterns
struct RepeatedPattern {
std::string pattern;
int length;
int position;
RepeatedPattern(const std::string& p, int l, int pos)
: pattern(p), length(l), position(pos) {}
};
static std::vector<RepeatedPattern> zAlgorithmFindRepeatedPatterns(const std::string& str) {
std::vector<int> z = computeZArray(str);
std::vector<RepeatedPattern> patterns;
for (int i = 1; i < z.size(); i++) {
if (z[i] > 0) {
std::string pattern = str.substr(0, z[i]);
if (z[i] >= pattern.length()) {
patterns.emplace_back(pattern, z[i], i);
}
}
}
return patterns;
}
// Z-Algorithm for string compression
static std::string zAlgorithmCompress(const std::string& str) {
std::vector<int> z = computeZArray(str);
std::string compressed;
int i = 0;
while (i < str.length()) {
if (z[i] > 0) {
// Found a repeated pattern
compressed += str.substr(0, z[i]) + "*";
i += z[i];
} else {
compressed += str[i];
i++;
}
}
return compressed;
}
// Z-Algorithm with performance measurement
struct ZAlgorithmResult {
std::vector<int> matches;
int count;
long long executionTime;
ZAlgorithmResult(const std::vector<int>& m, int c, long long t)
: matches(m), count(c), executionTime(t) {}
};
static ZAlgorithmResult zAlgorithmWithTiming(const std::string& text, const std::string& pattern) {
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> matches = zAlgorithmSearch(text, pattern);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
return ZAlgorithmResult(matches, matches.size(), duration.count());
}
// Z-Algorithm with detailed analysis
struct ZAlgorithmAnalysis {
std::string pattern;
int patternLength;
int textLength;
int combinedLength;
std::vector<int> zArray;
std::vector<int> matches;
int matchCount;
std::unordered_map<std::string, std::string> efficiency;
ZAlgorithmAnalysis(const std::string& p, int pLen, int tLen, int cLen,
const std::vector<int>& z, const std::vector<int>& m, int mCount)
: pattern(p), patternLength(pLen), textLength(tLen), combinedLength(cLen),
zArray(z), matches(m), matchCount(mCount) {
efficiency["comparisons"] = std::to_string(cLen);
efficiency["time_complexity"] = "O(n + m)";
efficiency["space_complexity"] = "O(n + m)";
}
};
static ZAlgorithmAnalysis zAlgorithmAnalyze(const std::string& text, const std::string& pattern) {
std::string combined = pattern + "
Loading AntInLoop...
quot; + text;
std::vector<int> z = computeZArray(combined);
std::vector<int> matches = zAlgorithmSearch(text, pattern);
return ZAlgorithmAnalysis(pattern, pattern.length(), text.length(),
combined.length(), z, matches, matches.size());
}
// Z-Algorithm for finding all suffixes that are also prefixes
struct SuffixPrefix {
std::string suffix;
std::string prefix;
int length;
SuffixPrefix(const std::string& s, const std::string& p, int l)
: suffix(s), prefix(p), length(l) {}
};
static std::vector<SuffixPrefix> zAlgorithmSuffixPrefix(const std::string& str) {
std::vector<int> z = computeZArray(str);
std::vector<SuffixPrefix> results;
for (int i = 1; i < z.size(); i++) {
if (z[i] > 0 && i + z[i] == str.length()) {
results.emplace_back(str.substr(i), str.substr(0, z[i]), z[i]);
}
}
return results;
}
// Performance comparison
static void comparePerformance(const std::string& text, const std::string& pattern) {
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> matches = zAlgorithmSearch(text, pattern);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Z-Algorithm Search: " << matches.size() << " matches found in "
<< duration.count() << " μs" << std::endl;
}
};JAVA Implementation
// Z-Algorithm Implementation in Java
import java.util.*;
public class ZAlgorithm {
// Compute Z-array for a given string
public static int[] computeZArray(String str) {
int n = str.length();
int[] z = new int[n];
// Z[0] is the length of the string itself
z[0] = n;
int left = 0, right = 0;
for (int i = 1; i < n; i++) {
if (i > right) {
// No Z-box found yet, expand from current position
left = right = i;
while (right < n && str.charAt(right - left) == str.charAt(right)) {
right++;
}
z[i] = right - left;
right--;
} else {
// We are inside a Z-box
int k = i - left;
if (z[k] < right - i + 1) {
// Z[k] is less than remaining length, copy it
z[i] = z[k];
} else {
// Z[k] is greater than or equal to remaining length, expand
left = i;
while (right < n && str.charAt(right - left) == str.charAt(right)) {
right++;
}
z[i] = right - left;
right--;
}
}
}
return z;
}
// Z-Algorithm for pattern matching
public static List<Integer> zAlgorithmSearch(String text, String pattern) {
String combined = pattern + "
Loading AntInLoop...
quot; + text;
int[] z = computeZArray(combined);
List<Integer> matches = new ArrayList<>();
int patternLength = pattern.length();
for (int i = patternLength + 1; i < z.length; i++) {
if (z[i] == patternLength) {
matches.add(i - patternLength - 1);
}
}
return matches;
}
// Z-Algorithm for finding all occurrences
public static List<Integer> zAlgorithmFindAll(String text, String pattern) {
return zAlgorithmSearch(text, pattern);
}
// Z-Algorithm for first occurrence
public static int zAlgorithmFirstMatch(String text, String pattern) {
List<Integer> matches = zAlgorithmSearch(text, pattern);
return matches.isEmpty() ? -1 : matches.get(0);
}
// Z-Algorithm for last occurrence
public static int zAlgorithmLastMatch(String text, String pattern) {
List<Integer> matches = zAlgorithmSearch(text, pattern);
return matches.isEmpty() ? -1 : matches.get(matches.size() - 1);
}
// Z-Algorithm for count only
public static int zAlgorithmCount(String text, String pattern) {
return zAlgorithmSearch(text, pattern).size();
}
// Z-Algorithm with case-insensitive search
public static List<Integer> zAlgorithmCaseInsensitive(String text, String pattern) {
return zAlgorithmSearch(text.toLowerCase(), pattern.toLowerCase());
}
// Z-Algorithm for multiple patterns
public static Map<String, List<Integer>> zAlgorithmMultiplePatterns(String text, String[] patterns) {
Map<String, List<Integer>> results = new HashMap<>();
for (String pattern : patterns) {
results.put(pattern, zAlgorithmSearch(text, pattern));
}
return results;
}
// Z-Algorithm for finding longest common prefix
public static int zAlgorithmLongestCommonPrefix(String str1, String str2) {
String combined = str1 + "
Loading AntInLoop...
quot; + str2;
int[] z = computeZArray(combined);
// Find the maximum Z value after the separator
int maxZ = 0;
for (int i = str1.length() + 1; i < z.length; i++) {
maxZ = Math.max(maxZ, z[i]);
}
return maxZ;
}
// Z-Algorithm for finding all palindromes
public static List<String> zAlgorithmFindPalindromes(String str) {
List<String> palindromes = new ArrayList<>();
int n = str.length();
for (int i = 0; i < n; i++) {
// Check odd length palindromes
String oddPalindrome = expandPalindrome(str, i, i);
if (oddPalindrome.length() > 1) {
palindromes.add(oddPalindrome);
}
// Check even length palindromes
if (i < n - 1) {
String evenPalindrome = expandPalindrome(str, i, i + 1);
if (evenPalindrome.length() > 1) {
palindromes.add(evenPalindrome);
}
}
}
return palindromes;
}
private static String expandPalindrome(String str, int left, int right) {
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
left--;
right++;
}
return str.substring(left + 1, right);
}
// Z-Algorithm for finding repeated patterns
public static List<Map<String, Object>> zAlgorithmFindRepeatedPatterns(String str) {
int[] z = computeZArray(str);
List<Map<String, Object>> patterns = new ArrayList<>();
for (int i = 1; i < z.length; i++) {
if (z[i] > 0) {
String pattern = str.substring(0, z[i]);
if (z[i] >= pattern.length()) {
Map<String, Object> patternInfo = new HashMap<>();
patternInfo.put("pattern", pattern);
patternInfo.put("length", z[i]);
patternInfo.put("position", i);
patterns.add(patternInfo);
}
}
}
return patterns;
}
// Z-Algorithm for string compression
public static String zAlgorithmCompress(String str) {
int[] z = computeZArray(str);
StringBuilder compressed = new StringBuilder();
int i = 0;
while (i < str.length()) {
if (z[i] > 0) {
// Found a repeated pattern
compressed.append(str.substring(0, z[i])).append("*");
i += z[i];
} else {
compressed.append(str.charAt(i));
i++;
}
}
return compressed.toString();
}
// Z-Algorithm with performance measurement
public static class ZAlgorithmResult {
public List<Integer> matches;
public int count;
public long executionTime;
public ZAlgorithmResult(List<Integer> matches, int count, long executionTime) {
this.matches = matches;
this.count = count;
this.executionTime = executionTime;
}
}
public static ZAlgorithmResult zAlgorithmWithTiming(String text, String pattern) {
long startTime = System.nanoTime();
List<Integer> matches = zAlgorithmSearch(text, pattern);
long endTime = System.nanoTime();
return new ZAlgorithmResult(matches, matches.size(), endTime - startTime);
}
// Z-Algorithm with detailed analysis
public static class ZAlgorithmAnalysis {
public String pattern;
public int patternLength;
public int textLength;
public int combinedLength;
public int[] zArray;
public List<Integer> matches;
public int matchCount;
public Map<String, String> efficiency;
public ZAlgorithmAnalysis(String pattern, int patternLength, int textLength,
int combinedLength, int[] zArray, List<Integer> matches, int matchCount) {
this.pattern = pattern;
this.patternLength = patternLength;
this.textLength = textLength;
this.combinedLength = combinedLength;
this.zArray = zArray;
this.matches = matches;
this.matchCount = matchCount;
this.efficiency = new HashMap<>();
this.efficiency.put("comparisons", String.valueOf(combinedLength));
this.efficiency.put("time_complexity", "O(n + m)");
this.efficiency.put("space_complexity", "O(n + m)");
}
}
public static ZAlgorithmAnalysis zAlgorithmAnalyze(String text, String pattern) {
String combined = pattern + "
Loading AntInLoop...
quot; + text;
int[] z = computeZArray(combined);
List<Integer> matches = zAlgorithmSearch(text, pattern);
return new ZAlgorithmAnalysis(pattern, pattern.length(), text.length(),
combined.length(), z, matches, matches.size());
}
// Z-Algorithm for finding all suffixes that are also prefixes
public static List<Map<String, Object>> zAlgorithmSuffixPrefix(String str) {
int[] z = computeZArray(str);
List<Map<String, Object>> results = new ArrayList<>();
for (int i = 1; i < z.length; i++) {
if (z[i] > 0 && i + z[i] == str.length()) {
Map<String, Object> result = new HashMap<>();
result.put("suffix", str.substring(i));
result.put("prefix", str.substring(0, z[i]));
result.put("length", z[i]);
results.add(result);
}
}
return results;
}
}JAVASCRIPT Implementation
// Z-Algorithm Implementation in JavaScript
// Compute Z-array for a given string
function computeZArray(str) {
const n = str.length;
const z = new Array(n).fill(0);
// Z[0] is the length of the string itself
z[0] = n;
let left = 0, right = 0;
for (let i = 1; i < n; i++) {
if (i > right) {
// No Z-box found yet, expand from current position
left = right = i;
while (right < n && str[right - left] === str[right]) {
right++;
}
z[i] = right - left;
right--;
} else {
// We are inside a Z-box
const k = i - left;
if (z[k] < right - i + 1) {
// Z[k] is less than remaining length, copy it
z[i] = z[k];
} else {
// Z[k] is greater than or equal to remaining length, expand
left = i;
while (right < n && str[right - left] === str[right]) {
right++;
}
z[i] = right - left;
right--;
}
}
}
return z;
}
// Z-Algorithm for pattern matching
function zAlgorithmSearch(text, pattern) {
const combined = pattern + '
Loading AntInLoop...
#39; + text;
const z = computeZArray(combined);
const matches = [];
const patternLength = pattern.length;
for (let i = patternLength + 1; i < z.length; i++) {
if (z[i] === patternLength) {
matches.push(i - patternLength - 1);
}
}
return matches;
}
// Z-Algorithm for finding all occurrences
function zAlgorithmFindAll(text, pattern) {
return zAlgorithmSearch(text, pattern);
}
// Z-Algorithm for first occurrence
function zAlgorithmFirstMatch(text, pattern) {
const matches = zAlgorithmSearch(text, pattern);
return matches.length > 0 ? matches[0] : -1;
}
// Z-Algorithm for last occurrence
function zAlgorithmLastMatch(text, pattern) {
const matches = zAlgorithmSearch(text, pattern);
return matches.length > 0 ? matches[matches.length - 1] : -1;
}
// Z-Algorithm for count only
function zAlgorithmCount(text, pattern) {
return zAlgorithmSearch(text, pattern).length;
}
// Z-Algorithm with case-insensitive search
function zAlgorithmCaseInsensitive(text, pattern) {
const lowerText = text.toLowerCase();
const lowerPattern = pattern.toLowerCase();
return zAlgorithmSearch(lowerText, lowerPattern);
}
// Z-Algorithm for multiple patterns
function zAlgorithmMultiplePatterns(text, patterns) {
const results = {};
for (const pattern of patterns) {
results[pattern] = zAlgorithmSearch(text, pattern);
}
return results;
}
// Z-Algorithm for finding longest common prefix
function zAlgorithmLongestCommonPrefix(str1, str2) {
const combined = str1 + '
Loading AntInLoop...
#39; + str2;
const z = computeZArray(combined);
// Find the maximum Z value after the separator
let maxZ = 0;
for (let i = str1.length + 1; i < z.length; i++) {
maxZ = Math.max(maxZ, z[i]);
}
return maxZ;
}
// Z-Algorithm for finding all palindromes
function zAlgorithmFindPalindromes(str) {
const palindromes = [];
const n = str.length;
for (let i = 0; i < n; i++) {
// Check odd length palindromes
const oddPalindrome = expandPalindrome(str, i, i);
if (oddPalindrome.length > 1) {
palindromes.push(oddPalindrome);
}
// Check even length palindromes
if (i < n - 1) {
const evenPalindrome = expandPalindrome(str, i, i + 1);
if (evenPalindrome.length > 1) {
palindromes.push(evenPalindrome);
}
}
}
return palindromes;
}
function expandPalindrome(str, left, right) {
while (left >= 0 && right < str.length && str[left] === str[right]) {
left--;
right++;
}
return str.substring(left + 1, right);
}
// Z-Algorithm for finding repeated patterns
function zAlgorithmFindRepeatedPatterns(str) {
const z = computeZArray(str);
const patterns = [];
for (let i = 1; i < z.length; i++) {
if (z[i] > 0) {
const pattern = str.substring(0, z[i]);
if (z[i] >= pattern.length) {
patterns.push({
pattern,
length: z[i],
position: i
});
}
}
}
return patterns;
}
// Z-Algorithm for string compression
function zAlgorithmCompress(str) {
const z = computeZArray(str);
let compressed = '';
let i = 0;
while (i < str.length) {
if (z[i] > 0) {
// Found a repeated pattern
compressed += str.substring(0, z[i]) + '*';
i += z[i];
} else {
compressed += str[i];
i++;
}
}
return compressed;
}
// Z-Algorithm with performance measurement
function zAlgorithmWithTiming(text, pattern) {
const startTime = performance.now();
const matches = zAlgorithmSearch(text, pattern);
const endTime = performance.now();
return {
matches,
count: matches.length,
executionTime: endTime - startTime
};
}
// Z-Algorithm with detailed analysis
function zAlgorithmAnalyze(text, pattern) {
const combined = pattern + '
Loading AntInLoop...
#39; + text;
const z = computeZArray(combined);
const matches = zAlgorithmSearch(text, pattern);
return {
pattern,
patternLength: pattern.length,
textLength: text.length,
combinedLength: combined.length,
zArray: z,
matches,
matchCount: matches.length,
efficiency: {
comparisons: combined.length,
timeComplexity: 'O(n + m)',
spaceComplexity: 'O(n + m)'
}
};
}
// Z-Algorithm for finding all suffixes that are also prefixes
function zAlgorithmSuffixPrefix(str) {
const z = computeZArray(str);
const results = [];
for (let i = 1; i < z.length; i++) {
if (z[i] > 0 && i + z[i] === str.length) {
results.push({
suffix: str.substring(i),
prefix: str.substring(0, z[i]),
length: z[i]
});
}
}
return results;
}PYTHON Implementation
# Z-Algorithm Implementation in Python
def compute_z_array(s):
"""Compute Z-array for a given string"""
n = len(s)
z = [0] * n
# Z[0] is the length of the string itself
z[0] = n
left = right = 0
for i in range(1, n):
if i > right:
# No Z-box found yet, expand from current position
left = right = i
while right < n and s[right - left] == s[right]:
right += 1
z[i] = right - left
right -= 1
else:
# We are inside a Z-box
k = i - left
if z[k] < right - i + 1:
# Z[k] is less than remaining length, copy it
z[i] = z[k]
else:
# Z[k] is greater than or equal to remaining length, expand
left = i
while right < n and s[right - left] == s[right]:
right += 1
z[i] = right - left
right -= 1
return z
def z_algorithm_search(text, pattern):
"""Z-Algorithm for pattern matching"""
combined = pattern + '
Loading AntInLoop...
#39; + text
z = compute_z_array(combined)
matches = []
pattern_length = len(pattern)
for i in range(pattern_length + 1, len(z)):
if z[i] == pattern_length:
matches.append(i - pattern_length - 1)
return matches
def z_algorithm_find_all(text, pattern):
"""Z-Algorithm for finding all occurrences"""
return z_algorithm_search(text, pattern)
def z_algorithm_first_match(text, pattern):
"""Z-Algorithm for first occurrence"""
matches = z_algorithm_search(text, pattern)
return matches[0] if matches else -1
def z_algorithm_last_match(text, pattern):
"""Z-Algorithm for last occurrence"""
matches = z_algorithm_search(text, pattern)
return matches[-1] if matches else -1
def z_algorithm_count(text, pattern):
"""Z-Algorithm for count only"""
return len(z_algorithm_search(text, pattern))
def z_algorithm_case_insensitive(text, pattern):
"""Z-Algorithm with case-insensitive search"""
return z_algorithm_search(text.lower(), pattern.lower())
def z_algorithm_multiple_patterns(text, patterns):
"""Z-Algorithm for multiple patterns"""
results = {}
for pattern in patterns:
results[pattern] = z_algorithm_search(text, pattern)
return results
def z_algorithm_longest_common_prefix(str1, str2):
"""Z-Algorithm for finding longest common prefix"""
combined = str1 + '
Loading AntInLoop...
#39; + str2
z = compute_z_array(combined)
# Find the maximum Z value after the separator
max_z = 0
for i in range(len(str1) + 1, len(z)):
max_z = max(max_z, z[i])
return max_z
def z_algorithm_find_palindromes(s):
"""Z-Algorithm for finding all palindromes"""
palindromes = []
n = len(s)
for i in range(n):
# Check odd length palindromes
odd_palindrome = expand_palindrome(s, i, i)
if len(odd_palindrome) > 1:
palindromes.append(odd_palindrome)
# Check even length palindromes
if i < n - 1:
even_palindrome = expand_palindrome(s, i, i + 1)
if len(even_palindrome) > 1:
palindromes.append(even_palindrome)
return palindromes
def expand_palindrome(s, left, right):
"""Helper function to expand palindrome from center"""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
def z_algorithm_find_repeated_patterns(s):
"""Z-Algorithm for finding repeated patterns"""
z = compute_z_array(s)
patterns = []
for i in range(1, len(z)):
if z[i] > 0:
pattern = s[:z[i]]
if z[i] >= len(pattern):
patterns.append({
'pattern': pattern,
'length': z[i],
'position': i
})
return patterns
def z_algorithm_compress(s):
"""Z-Algorithm for string compression"""
z = compute_z_array(s)
compressed = ""
i = 0
while i < len(s):
if z[i] > 0:
# Found a repeated pattern
compressed += s[:z[i]] + "*"
i += z[i]
else:
compressed += s[i]
i += 1
return compressed
def z_algorithm_with_timing(text, pattern):
"""Z-Algorithm with performance measurement"""
import time
start_time = time.time()
matches = z_algorithm_search(text, pattern)
end_time = time.time()
return {
'matches': matches,
'count': len(matches),
'execution_time': end_time - start_time
}
def z_algorithm_analyze(text, pattern):
"""Z-Algorithm with detailed analysis"""
combined = pattern + '
Loading AntInLoop...
#39; + text
z = compute_z_array(combined)
matches = z_algorithm_search(text, pattern)
return {
'pattern': pattern,
'pattern_length': len(pattern),
'text_length': len(text),
'combined_length': len(combined),
'z_array': z,
'matches': matches,
'match_count': len(matches),
'efficiency': {
'comparisons': len(combined),
'time_complexity': 'O(n + m)',
'space_complexity': 'O(n + m)'
}
}
def z_algorithm_suffix_prefix(s):
"""Z-Algorithm for finding all suffixes that are also prefixes"""
z = compute_z_array(s)
results = []
for i in range(1, len(z)):
if z[i] > 0 and i + z[i] == len(s):
results.append({
'suffix': s[i:],
'prefix': s[:z[i]],
'length': z[i]
})
return results
# Additional utilities
def z_algorithm_is_substring(text, pattern):
"""Check if pattern is a substring of text using Z-algorithm"""
return len(z_algorithm_search(text, pattern)) > 0
def z_algorithm_longest_repeated_substring(s):
"""Find longest repeated substring using Z-algorithm"""
max_length = 0
result = ""
for i in range(1, len(s)):
z = compute_z_array(s[i:])
for j in range(len(z)):
if z[j] > max_length and z[j] <= j:
max_length = z[j]
result = s[i:i + z[j]]
return result