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())
}