AhoCorasick.java

importjava.util.*;

publicclassAhoCorasick {

// Trie Node Class
staticclassTrieNode {
Map<Character, TrieNode> children = newHashMap<>();
TrieNodefailureLink = null;
List<String> output = newArrayList<>();
 }

privateTrieNoderoot = newTrieNode();

// Step 1: Build the Trie
publicvoidaddKeyword(Stringkeyword) {
TrieNodecurrentNode = root;
for (charc : keyword.toCharArray()) {
currentNode = currentNode.children.computeIfAbsent(c, k -> newTrieNode());
 }
currentNode.output.add(keyword);
 }

// Step 2: Build Failure Links
publicvoidbuildFailureLinks() {
Queue<TrieNode> queue = newLinkedList<>();
root.failureLink = root;
queue.add(root);

while (!queue.isEmpty()) {
TrieNodecurrent = queue.poll();

for (Map.Entry<Character, TrieNode> entry : current.children.entrySet()) {
charc = entry.getKey();
TrieNodechild = entry.getValue();

// Set failure link
TrieNodefailure = current.failureLink;
while (failure != root && !failure.children.containsKey(c)) {
failure = failure.failureLink;
 }

if (failure.children.containsKey(c) && failure.children.get(c) != child) {
child.failureLink = failure.children.get(c);
 } else {
child.failureLink = root;
 }

// Merge output from failure link
child.output.addAll(child.failureLink.output);
queue.add(child);
 }
 }
 }

// Step 3: Search the Text
publicList<String> search(Stringtext) {
List<String> results = newArrayList<>();
TrieNodecurrentNode = root;

for (charc : text.toCharArray()) {
while (currentNode != root && !currentNode.children.containsKey(c)) {
currentNode = currentNode.failureLink;
 }
if (currentNode.children.containsKey(c)) {
currentNode = currentNode.children.get(c);
 }

// Add matches to results
results.addAll(currentNode.output);
 }

returnresults;
 }

publicstaticvoidmain(String[] args) {
AhoCorasickac = newAhoCorasick();
ac.addKeyword("he");
ac.addKeyword("she");
ac.addKeyword("hers");
ac.addKeyword("his");

ac.buildFailureLinks();

List<String> matches = ac.search("ushers");
System.out.println("Matches found: " + matches);
 }
}