AntInLoop

Aho–Corasick Multi-Pattern Matching Algorithm Code Implementations

Complete Aho–Corasick Multi-Pattern Matching Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Aho–Corasick Multi-Pattern Matching Algorithm Guide · Launch Interactive Visualizer

C++ Implementation

// Aho-Corasick Algorithm Implementation in C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <queue>
#include <chrono>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord = false;
    TrieNode* failure = nullptr;
    std::vector<std::string> output;
};

class AhoCorasick {
private:
    TrieNode* root;
    
public:
    AhoCorasick() {
        root = new TrieNode();
    }
    
    ~AhoCorasick() {
        deleteTrie(root);
    }
    
    // Add pattern to trie
    void addPattern(const std::string& pattern) {
        TrieNode* current = root;
        
        for (char c : pattern) {
            if (current->children.find(c) == current->children.end()) {
                current->children[c] = new TrieNode();
            }
            current = current->children[c];
        }
        
        current->isEndOfWord = true;
        current->output.push_back(pattern);
    }
    
    // Build failure links
    void buildFailureLinks() {
        std::queue<TrieNode*> q;
        
        // Initialize failure links for depth 1
        for (auto& pair : root->children) {
            pair.second->failure = root;
            q.push(pair.second);
        }
        
        // Process remaining nodes
        while (!q.empty()) {
            TrieNode* current = q.front();
            q.pop();
            
            for (auto& pair : current->children) {
                char c = pair.first;
                TrieNode* child = pair.second;
                q.push(child);
                
                TrieNode* failure = current->failure;
                while (failure && failure->children.find(c) == failure->children.end()) {
                    failure = failure->failure;
                }
                
                child->failure = failure ? failure->children[c] : root;
                child->output.insert(child->output.end(), 
                                   child->failure->output.begin(), 
                                   child->failure->output.end());
            }
        }
    }
    
    // Search for all patterns in text
    std::unordered_map<std::string, std::vector<int>> search(const std::string& text) {
        std::unordered_map<std::string, std::vector<int>> results;
        TrieNode* current = root;
        
        for (int i = 0; i < text.length(); i++) {
            char c = text[i];
            
            // Follow failure links until we find a match or reach root
            while (current && current->children.find(c) == current->children.end()) {
                current = current->failure;
            }
            
            current = current ? current->children[c] : root;
            
            // Check for matches at current node
            for (const std::string& pattern : current->output) {
                results[pattern].push_back(i - pattern.length() + 1);
            }
        }
        
        return results;
    }
    
    // Search with case-insensitive matching
    std::unordered_map<std::string, std::vector<int>> searchCaseInsensitive(std::string text) {
        std::transform(text.begin(), text.end(), text.begin(), ::tolower);
        return search(text);
    }
    
    // Get all matches as vector
    struct Match {
        std::string pattern;
        int position;
        std::string text;
        
        Match(const std::string& p, int pos, const std::string& t) 
            : pattern(p), position(pos), text(t) {}
    };
    
    std::vector<Match> getAllMatches(const std::string& text) {
        auto results = search(text);
        std::vector<Match> matches;
        
        for (const auto& pair : results) {
            const std::string& pattern = pair.first;
            for (int pos : pair.second) {
                matches.emplace_back(pattern, pos, 
                                   text.substr(pos, pattern.length()));
            }
        }
        
        std::sort(matches.begin(), matches.end(), 
                 [](const Match& a, const Match& b) { return a.position < b.position; });
        return matches;
    }
    
    // Count occurrences of each pattern
    std::unordered_map<std::string, int> countMatches(const std::string& text) {
        auto results = search(text);
        std::unordered_map<std::string, int> counts;
        
        for (const auto& pair : results) {
            counts[pair.first] = pair.second.size();
        }
        
        return counts;
    }
    
    // Find first occurrence of each pattern
    std::unordered_map<std::string, int> findFirstMatches(const std::string& text) {
        auto results = search(text);
        std::unordered_map<std::string, int> firstMatches;
        
        for (const auto& pair : results) {
            firstMatches[pair.first] = pair.second[0];
        }
        
        return firstMatches;
    }
    
    // Check if any pattern exists in text
    bool hasAnyMatch(const std::string& text) {
        auto results = search(text);
        return !results.empty();
    }
    
    // Get patterns that match in text
    std::vector<std::string> getMatchingPatterns(const std::string& text) {
        auto results = search(text);
        std::vector<std::string> patterns;
        
        for (const auto& pair : results) {
            patterns.push_back(pair.first);
        }
        
        return patterns;
    }
    
private:
    void deleteTrie(TrieNode* node) {
        if (!node) return;
        
        for (auto& pair : node->children) {
            deleteTrie(pair.second);
        }
        delete node;
    }
    
public:
    // Utility method to create Aho-Corasick from patterns
    static AhoCorasick createFromPatterns(const std::vector<std::string>& patterns) {
        AhoCorasick ac;
        
        for (const std::string& pattern : patterns) {
            ac.addPattern(pattern);
        }
        
        ac.buildFailureLinks();
        return ac;
    }
    
    // Search multiple patterns in text
    static std::unordered_map<std::string, std::vector<int>> searchMultiplePatterns(
        const std::string& text, const std::vector<std::string>& patterns) {
        AhoCorasick ac = createFromPatterns(patterns);
        return ac.search(text);
    }
    
    // Search with timing
    struct SearchResult {
        std::unordered_map<std::string, std::vector<int>> results;
        long long executionTime;
        int patternCount;
        int matchCount;
        
        SearchResult(const std::unordered_map<std::string, std::vector<int>>& r, 
                    long long time, int pCount, int mCount) 
            : results(r), executionTime(time), patternCount(pCount), matchCount(mCount) {}
    };
    
    static SearchResult searchWithTiming(const std::string& text, const std::vector<std::string>& patterns) {
        auto start = std::chrono::high_resolution_clock::now();
        AhoCorasick ac = createFromPatterns(patterns);
        auto results = ac.search(text);
        auto end = std::chrono::high_resolution_clock::now();
        
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        
        int matchCount = 0;
        for (const auto& pair : results) {
            matchCount += pair.second.size();
        }
        
        return SearchResult(results, duration.count(), patterns.size(), matchCount);
    }
    
    // Performance comparison
    static void comparePerformance(const std::string& text, const std::vector<std::string>& patterns) {
        auto start = std::chrono::high_resolution_clock::now();
        AhoCorasick ac = createFromPatterns(patterns);
        auto results = ac.search(text);
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        
        int matchCount = 0;
        for (const auto& pair : results) {
            matchCount += pair.second.size();
        }
        
        std::cout << "Aho-Corasick Search: " << matchCount << " matches found in " 
                  << duration.count() << " μs" << std::endl;
        std::cout << "Patterns: " << patterns.size() << std::endl;
    }
};

JAVA Implementation

// Aho-Corasick Algorithm Implementation in Java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
    TrieNode failure = null;
    List<String> output = new ArrayList<>();
}

public class AhoCorasick {
    private TrieNode root;
    
    public AhoCorasick() {
        this.root = new TrieNode();
    }
    
    // Add pattern to trie
    public void addPattern(String pattern) {
        TrieNode current = root;
        
        for (char c : pattern.toCharArray()) {
            current.children.putIfAbsent(c, new TrieNode());
            current = current.children.get(c);
        }
        
        current.isEndOfWord = true;
        current.output.add(pattern);
    }
    
    // Build failure links
    public void buildFailureLinks() {
        Queue<TrieNode> queue = new LinkedList<>();
        
        // Initialize failure links for depth 1
        for (TrieNode child : root.children.values()) {
            child.failure = root;
            queue.offer(child);
        }
        
        // Process remaining nodes
        while (!queue.isEmpty()) {
            TrieNode current = queue.poll();
            
            for (Map.Entry<Character, TrieNode> entry : current.children.entrySet()) {
                char c = entry.getKey();
                TrieNode child = entry.getValue();
                queue.offer(child);
                
                TrieNode failure = current.failure;
                while (failure != null && !failure.children.containsKey(c)) {
                    failure = failure.failure;
                }
                
                child.failure = failure != null ? failure.children.get(c) : root;
                child.output.addAll(child.failure.output);
            }
        }
    }
    
    // Search for all patterns in text
    public Map<String, List<Integer>> search(String text) {
        Map<String, List<Integer>> results = new HashMap<>();
        TrieNode current = root;
        
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            
            // Follow failure links until we find a match or reach root
            while (current != null && !current.children.containsKey(c)) {
                current = current.failure;
            }
            
            current = current != null ? current.children.get(c) : root;
            
            // Check for matches at current node
            for (String pattern : current.output) {
                results.computeIfAbsent(pattern, k -> new ArrayList<>())
                      .add(i - pattern.length() + 1);
            }
        }
        
        return results;
    }
    
    // Search with case-insensitive matching
    public Map<String, List<Integer>> searchCaseInsensitive(String text) {
        return search(text.toLowerCase());
    }
    
    // Get all matches as list
    public List<Map<String, Object>> getAllMatches(String text) {
        Map<String, List<Integer>> results = search(text);
        List<Map<String, Object>> matches = new ArrayList<>();
        
        for (Map.Entry<String, List<Integer>> entry : results.entrySet()) {
            String pattern = entry.getKey();
            for (Integer pos : entry.getValue()) {
                Map<String, Object> match = new HashMap<>();
                match.put("pattern", pattern);
                match.put("position", pos);
                match.put("text", text.substring(pos, pos + pattern.length()));
                matches.add(match);
            }
        }
        
        matches.sort((a, b) -> (Integer) a.get("position") - (Integer) b.get("position"));
        return matches;
    }
    
    // Count occurrences of each pattern
    public Map<String, Integer> countMatches(String text) {
        Map<String, List<Integer>> results = search(text);
        Map<String, Integer> counts = new HashMap<>();
        
        for (Map.Entry<String, List<Integer>> entry : results.entrySet()) {
            counts.put(entry.getKey(), entry.getValue().size());
        }
        
        return counts;
    }
    
    // Find first occurrence of each pattern
    public Map<String, Integer> findFirstMatches(String text) {
        Map<String, List<Integer>> results = search(text);
        Map<String, Integer> firstMatches = new HashMap<>();
        
        for (Map.Entry<String, List<Integer>> entry : results.entrySet()) {
            firstMatches.put(entry.getKey(), entry.getValue().get(0));
        }
        
        return firstMatches;
    }
    
    // Check if any pattern exists in text
    public boolean hasAnyMatch(String text) {
        Map<String, List<Integer>> results = search(text);
        return !results.isEmpty();
    }
    
    // Get patterns that match in text
    public Set<String> getMatchingPatterns(String text) {
        Map<String, List<Integer>> results = search(text);
        return results.keySet();
    }
    
    // Utility method to create Aho-Corasick from patterns
    public static AhoCorasick createFromPatterns(List<String> patterns) {
        AhoCorasick ac = new AhoCorasick();
        
        for (String pattern : patterns) {
            ac.addPattern(pattern);
        }
        
        ac.buildFailureLinks();
        return ac;
    }
    
    // Search multiple patterns in text
    public static Map<String, List<Integer>> searchMultiplePatterns(String text, List<String> patterns) {
        AhoCorasick ac = createFromPatterns(patterns);
        return ac.search(text);
    }
    
    // Search with timing
    public static class SearchResult {
        public Map<String, List<Integer>> results;
        public long executionTime;
        public int patternCount;
        public int matchCount;
        
        public SearchResult(Map<String, List<Integer>> results, long executionTime, 
                          int patternCount, int matchCount) {
            this.results = results;
            this.executionTime = executionTime;
            this.patternCount = patternCount;
            this.matchCount = matchCount;
        }
    }
    
    public static SearchResult searchWithTiming(String text, List<String> patterns) {
        long startTime = System.nanoTime();
        AhoCorasick ac = createFromPatterns(patterns);
        Map<String, List<Integer>> results = ac.search(text);
        long endTime = System.nanoTime();
        
        int matchCount = results.values().stream().mapToInt(List::size).sum();
        
        return new SearchResult(results, endTime - startTime, patterns.size(), matchCount);
    }
}

JAVASCRIPT Implementation

// Aho-Corasick Algorithm Implementation in JavaScript

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
    this.failure = null;
    this.output = [];
  }
}

class AhoCorasick {
  constructor() {
    this.root = new TrieNode();
  }
  
  // Add pattern to trie
  addPattern(pattern) {
    let current = this.root;
    
    for (const char of pattern) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    
    current.isEndOfWord = true;
    current.output.push(pattern);
  }
  
  // Build failure links
  buildFailureLinks() {
    const queue = [];
    
    // Initialize failure links for depth 1
    for (const [char, child] of this.root.children) {
      child.failure = this.root;
      queue.push(child);
    }
    
    // Process remaining nodes
    while (queue.length > 0) {
      const current = queue.shift();
      
      for (const [char, child] of current.children) {
        queue.push(child);
        
        let failure = current.failure;
        while (failure && !failure.children.has(char)) {
          failure = failure.failure;
        }
        
        child.failure = failure ? failure.children.get(char) : this.root;
        child.output.push(...child.failure.output);
      }
    }
  }
  
  // Search for all patterns in text
  search(text) {
    const results = new Map();
    let current = this.root;
    
    for (let i = 0; i < text.length; i++) {
      const char = text[i];
      
      // Follow failure links until we find a match or reach root
      while (current && !current.children.has(char)) {
        current = current.failure;
      }
      
      current = current ? current.children.get(char) : this.root;
      
      // Check for matches at current node
      for (const pattern of current.output) {
        if (!results.has(pattern)) {
          results.set(pattern, []);
        }
        results.get(pattern).push(i - pattern.length + 1);
      }
    }
    
    return results;
  }
  
  // Search with case-insensitive matching
  searchCaseInsensitive(text) {
    const lowerText = text.toLowerCase();
    const results = this.search(lowerText);
    
    // Convert results back to original case
    const originalResults = new Map();
    for (const [pattern, positions] of results) {
      originalResults.set(pattern, positions);
    }
    
    return originalResults;
  }
  
  // Get all matches as array
  getAllMatches(text) {
    const results = this.search(text);
    const matches = [];
    
    for (const [pattern, positions] of results) {
      for (const pos of positions) {
        matches.push({
          pattern,
          position: pos,
          text: text.substring(pos, pos + pattern.length)
        });
      }
    }
    
    return matches.sort((a, b) => a.position - b.position);
  }
  
  // Count occurrences of each pattern
  countMatches(text) {
    const results = this.search(text);
    const counts = new Map();
    
    for (const [pattern, positions] of results) {
      counts.set(pattern, positions.length);
    }
    
    return counts;
  }
  
  // Find first occurrence of each pattern
  findFirstMatches(text) {
    const results = this.search(text);
    const firstMatches = new Map();
    
    for (const [pattern, positions] of results) {
      firstMatches.set(pattern, positions[0]);
    }
    
    return firstMatches;
  }
  
  // Check if any pattern exists in text
  hasAnyMatch(text) {
    const results = this.search(text);
    return results.size > 0;
  }
  
  // Get patterns that match in text
  getMatchingPatterns(text) {
    const results = this.search(text);
    return Array.from(results.keys());
  }
}

// Utility function to create Aho-Corasick from patterns
function createAhoCorasick(patterns) {
  const ac = new AhoCorasick();
  
  for (const pattern of patterns) {
    ac.addPattern(pattern);
  }
  
  ac.buildFailureLinks();
  return ac;
}

// Search multiple patterns in text
function searchMultiplePatterns(text, patterns) {
  const ac = createAhoCorasick(patterns);
  return ac.search(text);
}

// Find all matches with timing
function searchWithTiming(text, patterns) {
  const startTime = performance.now();
  const ac = createAhoCorasick(patterns);
  const results = ac.search(text);
  const endTime = performance.now();
  
  return {
    results,
    executionTime: endTime - startTime,
    patternCount: patterns.length,
    matchCount: Array.from(results.values()).reduce((sum, positions) => sum + positions.length, 0)
  };
}

PYTHON Implementation

# Aho-Corasick Algorithm Implementation in Python

from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False
        self.failure = None
        self.output = []

class AhoCorasick:
    def __init__(self):
        self.root = TrieNode()
    
    def add_pattern(self, pattern):
        """Add pattern to trie"""
        current = self.root
        
        for char in pattern:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        
        current.is_end_of_word = True
        current.output.append(pattern)
    
    def build_failure_links(self):
        """Build failure links"""
        queue = []
        
        # Initialize failure links for depth 1
        for char, child in self.root.children.items():
            child.failure = self.root
            queue.append(child)
        
        # Process remaining nodes
        while queue:
            current = queue.pop(0)
            
            for char, child in current.children.items():
                queue.append(child)
                
                failure = current.failure
                while failure and char not in failure.children:
                    failure = failure.failure
                
                child.failure = failure.children.get(char) if failure else self.root
                child.output.extend(child.failure.output)
    
    def search(self, text):
        """Search for all patterns in text"""
        results = defaultdict(list)
        current = self.root
        
        for i, char in enumerate(text):
            # Follow failure links until we find a match or reach root
            while current and char not in current.children:
                current = current.failure
            
            current = current.children.get(char) if current else self.root
            
            # Check for matches at current node
            for pattern in current.output:
                results[pattern].append(i - len(pattern) + 1)
        
        return dict(results)
    
    def search_case_insensitive(self, text):
        """Search with case-insensitive matching"""
        return self.search(text.lower())
    
    def get_all_matches(self, text):
        """Get all matches as list"""
        results = self.search(text)
        matches = []
        
        for pattern, positions in results.items():
            for pos in positions:
                matches.append({
                    'pattern': pattern,
                    'position': pos,
                    'text': text[pos:pos + len(pattern)]
                })
        
        return sorted(matches, key=lambda x: x['position'])
    
    def count_matches(self, text):
        """Count occurrences of each pattern"""
        results = self.search(text)
        return {pattern: len(positions) for pattern, positions in results.items()}
    
    def find_first_matches(self, text):
        """Find first occurrence of each pattern"""
        results = self.search(text)
        return {pattern: positions[0] for pattern, positions in results.items()}
    
    def has_any_match(self, text):
        """Check if any pattern exists in text"""
        results = self.search(text)
        return len(results) > 0
    
    def get_matching_patterns(self, text):
        """Get patterns that match in text"""
        results = self.search(text)
        return list(results.keys())

def create_aho_corasick(patterns):
    """Utility function to create Aho-Corasick from patterns"""
    ac = AhoCorasick()
    
    for pattern in patterns:
        ac.add_pattern(pattern)
    
    ac.build_failure_links()
    return ac

def search_multiple_patterns(text, patterns):
    """Search multiple patterns in text"""
    ac = create_aho_corasick(patterns)
    return ac.search(text)

def search_with_timing(text, patterns):
    """Find all matches with timing"""
    import time
    start_time = time.time()
    ac = create_aho_corasick(patterns)
    results = ac.search(text)
    end_time = time.time()
    
    return {
        'results': results,
        'execution_time': end_time - start_time,
        'pattern_count': len(patterns),
        'match_count': sum(len(positions) for positions in results.values())
    }