AntInLoop

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