Repository: TheAlgorithms/Java
Pull request #4465 (2023-09-30 22:15:33)

Add `AhoCorasick`
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


Prabhat-Kumar-42: Hey,
I added code for the Aho-Corasick algorithm.
This code should work for all the test cases.
Please review it, if any issue arises, please let me know.
I hope It will help the community.
Thank You !! :)
Manish-Rawat-1186: bro how did you convert into clang format

Prabhat-Kumar-42: > bro how did you convert into clang format
            
Hey, below are the steps for clang.
You can format your code with the command (run it somewhere _inside_ this project directory):
```shell
clang-format -i --style=file path/to/your/file.java
```
If you do not have the correct version of `clang-format` (i.e. < 16.0), you can remove this line:
https://github.com/TheAlgorithms/Java/blob/ea0eef128db5b3e5e1f9d58cb8a7e009cd508ead/.clang-format#L86
and add the _new line symbol_ at the end of your file manually (but do not commit the changed `.clang-format` file).

If you use gitpod, everything should run smoothly there.

_Originally posted by @vil02 in https://github.com/TheAlgorithms/Java/issues/4438#issuecomment-1741399556_
            
Prabhat-Kumar-42: I request the maintainer(s) to please merge my request using "hacktoberfest-accepted" label.
Thank You !!
Prabhat-Kumar-42: 
> Interesting contribution!
> 
> The code is quite complex - it could be simplified by introducing some new _helper_ methods. It is not easy, but we will make it perfect!

Thank You @vil02 , and yes I agree with code being complex. People often face problem understanding AhoCorasick.
And Yes We Will make it perfect.   

I have made the changes you mentioned, and I've also added some more test cases along with the one you mentioned. Please review it.

If there's any issue regarding the code, please do tell me. I will fix it as soon as possible.

Thank you.


vil02: > And Yes We Will make it perfect.

That is the spirit!
Prabhat-Kumar-42: > The `AhoCorasick` is quite big and I would suggest to cut it a bit.
> 
> What do you think about introducing a class called `Trie`. It should have:
> 
> * only one member `root`. It should have one constructor taking the `patterns`,
> * one method `searchIn` taking the `text`.
>   The constructor would do the same as `buildTrie` and `buildSuffixAndOutputLinks`. The `searchIn` would return the data, which is currently stored in `res`.
> 
> The mentioned methods are the only ones, which need to `public`. Some methods like `clear()` are not needed.
> 
> For time being, everything can happen within `AhoCorasick`. One could think about giving it a `static` method `Map<String, ArrayList<Integer>> search(String text, String[] patterns);`. And a `private static` method doing the conversion from convert `ArrayList<ArrayList<Integer>>` to `Map<String, ArrayList<Integer>>`.

Hey @vil02,

Since you asked to make modifications to the code and make new classes, i.e, Trie and AhoCorasick, I would like some suggestions on how should I structure these classes so It's organised and  benefits the Project. I have few options I have provided below.

### Option 1: Separate Files

Should I structure the code like this:
```
thealgorithms/
│   └── strings/
│       ├── AhoCorasick.java
│       ├── AhoCorasickTrie.java
│       ├── AhoCorasickTrieNode.java
│       └── OtherClasses/
└── OtherPackages/
```
In this option, `AhoCorasickTrieNode`, `AhoCorasickTrie`, and `AhoCorasick` have their separate classes in separate files, which helps with modularity and code manageability. `AhoCorasickTrieNode` implements the node of `AhoCorasickTrie`, `AhoCorasickTrie` implements the features you mentioned earlier, and `AhoCorasick` implements the static methods you mentioned.


### Option 2: Utility Package

Or should I structure it like this:
```
thealgorithms/
│   └── strings/
│             ├── AhoCorasick.java
│             ├── AhoCorasickUtilities/
│             │       ├── AhoCorasickTrie.java
│             │       └── AhoCorasickTrieNode.java
│             └── OtherClasses/
└── OtherPackages/
```
In this option, everything remains the same as in Option 1, but `AhoCorasickTrie.java` and `AhoCorasickTrieNode.java` are stored in the `AhoCorasickUtilities` package for ease of access and separation.

### Option 3: Inner Classes

Or should I make `Node` and `Trie` inner classes of the `AhoCorasick` class to keep the code in the same place?

Please advise on the best approach for code organization and project structure. Thank you!

vil02: @Prabhat-Kumar-42 I think that in case of this repository the **Option 3: Inner Classes** is the way to go.

The other suggestions are of curse the generally preferred ways, but they do not fit into this projects structure (usually there is _one algorithm - one file_ approach; there are exceptions, e.g. [`MedianOfRunningArray.java`](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java), [`MedianOfRunningArrayDouble.java`](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfRunningArrayDouble.java), [`MedianOfRunningArrayFloat.java`](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfRunningArrayFloat.java)). A good thing is that the resulting file will not be that long.
Prabhat-Kumar-42: > @Prabhat-Kumar-42 I think that in case of this repository the **Option 3: Inner Classes** is the way to go.
> 
> The other suggestions are of curse the generally preferred ways, but they do not fit into this projects structure (usually there is _one algorithm - one file_ approach; there are exceptions, e.g. [`MedianOfRunningArray.java`](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java), [`MedianOfRunningArrayDouble.java`](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfRunningArrayDouble.java), [`MedianOfRunningArrayFloat.java`](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfRunningArrayFloat.java)). A good thing is that the resulting file will not be that long.

I appreciate your feedback. I will Implement **Option 3: Inner Classes**.

Also, I have one more thing that I need your take on - 

 - since you mentioned keeping some members private (e.g. - `private static method doing the conversion from convert ArrayList<ArrayList<Integer>> to Map<String, ArrayList<Integer>>`). It won't be possible to test them in the test file as they can't be accessed. 

 - should I make these functions public or just test the available public methods and members of the code? 

Thank You !!
Prabhat-Kumar-42: > The `AhoCorasick` is quite big and I would suggest to cut it a bit.
> 
> What do you think about introducing a class called `Trie`. It should have:
> 
> * only one member `root`. It should have one constructor taking the `patterns`,
> * one method `searchIn` taking the `text`.
>   The constructor would do the same as `buildTrie` and `buildSuffixAndOutputLinks`. The `searchIn` would return the data, which is currently stored in `res`.
> 
> The mentioned methods are the only ones, which need to `public`. Some methods like `clear()` are not needed.
> 
> For time being, everything can happen within `AhoCorasick`. One could think about giving it a `static` method `Map<String, ArrayList<Integer>> search(String text, String[] patterns);`. And a `private static` method doing the conversion from convert `ArrayList<ArrayList<Integer>>` to `Map<String, ArrayList<Integer>>`.



> @Prabhat-Kumar-42 I think that in case of this repository the **Option 3: Inner Classes** is the way to go.


Hey @vil02 ,

I have implemented the changes you mentioned. I have kept the File Structure as **Option 3: Inner Classes**:

- Added Class Trie:
  - It has only one method, `searchIn(text)`, returning data stored in `res`.
  - The constructor would do the same as `buildTrie` and `buildSuffixAndOutputLinks`.

- AhoCorasick:
  - It has static methods: `Map<String, ArrayList<Integer>> search(String text, String[] patterns)` and `private static Map<String, ArrayList<Integer>> convert(ArrayList<ArrayList<Integer>>)`.

- Removed unimportant methods:
  - `clear()`.

- Updated Test Cases According to the updated AhoCorasick Source File.

There's one thing to note: Instead of having only a single member `root`, I have added `patterns` and `res` as members too, so methods don't look too complicated with lengthy parameters passing through them.

Please review it.

If there's any issue regarding the code, please do tell me. I will fix it as soon as possible.

Thank you.

Prabhat-Kumar-42: Hey @vil02 ,

I have updated the issues you have mentioned.

Please review the code.

Thank You !!
Prabhat-Kumar-42: Hey @vil02 ,

I have updated the changes you have mentioned.

Please review the code.

If there's anything that needs to be modified, please let me know.

Thank You !!
Prabhat-Kumar-42: Hey @vil02 ,

I have updated the changes you have mentioned.

I tried what you said above about wrapping up pattern indexing in another class. I hope you like it.

Please review the code.

If there's anything that needs to be modified, please let me know.

Thank You !!
vil02: @Prabhat-Kumar-42 wow, this was a pull-request. Thanks!

Patch:
diff --git a/src/main/java/com/thealgorithms/strings/AhoCorasick.java b/src/main/java/com/thealgorithms/strings/AhoCorasick.java
new file mode 100644
index 00000000..6381830c
--- /dev/null
+++ b/src/main/java/com/thealgorithms/strings/AhoCorasick.java
@@ -0,0 +1,249 @@
+/*
+ * Aho-Corasick String Matching Algorithm Implementation
+ *
+ * This code implements the Aho-Corasick algorithm, which is used for efficient
+ * string matching in a given text. It can find multiple patterns simultaneously
+ * and records their positions in the text.
+ *
+ * Author: Prabhat-Kumar-42
+ * GitHub: https://github.com/Prabhat-Kumar-42
+ */
+
+package com.thealgorithms.strings;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Queue;
+
+public final class AhoCorasick {
+    private AhoCorasick() {
+    }
+
+    // Trie Node Class
+    private static class Node {
+        // Represents a character in the trie
+        private HashMap<Character, Node> child = new HashMap<>(); // Child nodes of the current node
+        private Node suffixLink; // Suffix link to another node in the trie
+        private Node outputLink; // Output link to another node in the trie
+        private int patternInd; // Index of the pattern that ends at this node
+
+        Node() {
+            this.suffixLink = null;
+            this.outputLink = null;
+            this.patternInd = -1;
+        }
+
+        public HashMap<Character, Node> getChild() {
+            return child;
+        }
+
+        public Node getSuffixLink() {
+            return suffixLink;
+        }
+
+        public void setSuffixLink(final Node suffixLink) {
+            this.suffixLink = suffixLink;
+        }
+
+        public Node getOutputLink() {
+            return outputLink;
+        }
+
+        public void setOutputLink(final Node outputLink) {
+            this.outputLink = outputLink;
+        }
+
+        public int getPatternInd() {
+            return patternInd;
+        }
+
+        public void setPatternInd(final int patternInd) {
+            this.patternInd = patternInd;
+        }
+    }
+
+    // Trie Class
+    public static class Trie {
+
+        private Node root = null; // Root node of the trie
+        private final String[] patterns; // patterns according to which Trie is constructed
+
+        public Trie(final String[] patterns) {
+            root = new Node(); // Initialize the root of the trie
+            this.patterns = patterns;
+            buildTrie();
+            buildSuffixAndOutputLinks();
+        }
+
+        // builds AhoCorasick Trie
+        private void buildTrie() {
+
+            // Loop through each input pattern and building Trie
+            for (int i = 0; i < patterns.length; i++) {
+                Node curr = root; // Start at the root of the trie for each pattern
+
+                // Loop through each character in the current pattern
+                for (int j = 0; j < patterns[i].length(); j++) {
+                    char c = patterns[i].charAt(j); // Get the current character
+
+                    // Check if the current node has a child for the current character
+                    if (curr.getChild().containsKey(c)) {
+                        curr = curr.getChild().get(c); // Update the current node to the child node
+                    } else {
+                        // If no child node exists, create a new one and add it to the current node's children
+                        Node nn = new Node();
+                        curr.getChild().put(c, nn);
+                        curr = nn; // Update the current node to the new child node
+                    }
+                }
+                curr.setPatternInd(i); // Store the index of the pattern in the current leaf node
+            }
+        }
+
+        private void initializeSuffixLinksForChildNodesOfTheRoot(Queue<Node> q) {
+            for (char rc : root.getChild().keySet()) {
+                Node childNode = root.getChild().get(rc);
+                q.add(childNode); // Add child node to the queue
+                childNode.setSuffixLink(root); // Set suffix link to the root
+            }
+        }
+
+        private void buildSuffixAndOutputLinks() {
+            root.setSuffixLink(root); // Initialize the suffix link of the root to itself
+            Queue<Node> q = new LinkedList<>(); // Initialize a queue for BFS traversal
+
+            initializeSuffixLinksForChildNodesOfTheRoot(q);
+
+            while (!q.isEmpty()) {
+                Node currentState = q.poll(); // Get the current node for processing
+
+                // Iterate through child nodes of the current node
+                for (char cc : currentState.getChild().keySet()) {
+                    Node currentChild = currentState.getChild().get(cc); // Get the child node
+                    Node parentSuffix = currentState.getSuffixLink(); // Get the parent's suffix link
+
+                    // Calculate the suffix link for the child based on the parent's suffix link
+                    while (!parentSuffix.getChild().containsKey(cc) && parentSuffix != root) {
+                        parentSuffix = parentSuffix.getSuffixLink();
+                    }
+
+                    // Set the calculated suffix link or default to root
+                    if (parentSuffix.getChild().containsKey(cc)) {
+                        currentChild.setSuffixLink(parentSuffix.getChild().get(cc));
+                    } else {
+                        currentChild.setSuffixLink(root);
+                    }
+
+                    q.add(currentChild); // Add the child node to the queue for further processing
+                }
+
+                // Establish output links for nodes to efficiently identify patterns within patterns
+                if (currentState.getSuffixLink().getPatternInd() >= 0) {
+                    currentState.setOutputLink(currentState.getSuffixLink());
+                } else {
+                    currentState.setOutputLink(currentState.getSuffixLink().getOutputLink());
+                }
+            }
+        }
+
+        private ArrayList<ArrayList<Integer>> initializePositionByStringIndexValue() {
+            ArrayList<ArrayList<Integer>> positionByStringIndexValue = new ArrayList<>(patterns.length); // Stores positions where patterns are found in the text
+            for (int i = 0; i < patterns.length; i++) {
+                positionByStringIndexValue.add(new ArrayList<Integer>());
+            }
+            return positionByStringIndexValue;
+        }
+
+        // Searches for patterns in the input text and records their positions
+        public ArrayList<ArrayList<Integer>> searchIn(final String text) {
+            var positionByStringIndexValue = initializePositionByStringIndexValue(); // Initialize a list to store positions of the current pattern
+            Node parent = root; // Start searching from the root node
+
+            PatternPositionRecorder positionRecorder = new PatternPositionRecorder(positionByStringIndexValue);
+
+            for (int i = 0; i < text.length(); i++) {
+                char ch = text.charAt(i); // Get the current character in the text
+
+                // Check if the current node has a child for the current character
+                if (parent.getChild().containsKey(ch)) {
+                    parent = parent.getChild().get(ch); // Update the current node to the child node
+                    positionRecorder.recordPatternPositions(parent, i); // Use the method in PatternPositionRecorder to record positions
+                } else {
+                    // If no child node exists for the character, backtrack using suffix links
+                    while (parent != root && !parent.getChild().containsKey(ch)) {
+                        parent = parent.getSuffixLink();
+                    }
+                    if (parent.getChild().containsKey(ch)) {
+                        i--; // Decrement i to reprocess the same character
+                    }
+                }
+            }
+
+            setUpStartPoints(positionByStringIndexValue);
+            return positionByStringIndexValue;
+        }
+
+        // by default positionByStringIndexValue contains end-points. This function converts those
+        // endpoints to start points
+        private void setUpStartPoints(ArrayList<ArrayList<Integer>> positionByStringIndexValue) {
+            for (int i = 0; i < patterns.length; i++) {
+                for (int j = 0; j < positionByStringIndexValue.get(i).size(); j++) {
+                    int endpoint = positionByStringIndexValue.get(i).get(j);
+                    positionByStringIndexValue.get(i).set(j, endpoint - patterns[i].length() + 1);
+                }
+            }
+        }
+    }
+
+    // Class to handle pattern position recording
+    private static class PatternPositionRecorder {
+        private ArrayList<ArrayList<Integer>> positionByStringIndexValue;
+
+        // Constructor to initialize the recorder with the position list
+        PatternPositionRecorder(final ArrayList<ArrayList<Integer>> positionByStringIndexValue) {
+            this.positionByStringIndexValue = positionByStringIndexValue;
+        }
+
+        /**
+         * Records positions for a pattern when it's found in the input text and follows
+         * output links to record positions of other patterns.
+         *
+         * @param parent The current node representing a character in the pattern trie.
+         * @param currentPosition      The current position in the input text.
+         */
+        public void recordPatternPositions(final Node parent, final int currentPosition) {
+            // Check if the current node represents the end of a pattern
+            if (parent.getPatternInd() > -1) {
+                // Add the current position to the list of positions for the found pattern
+                positionByStringIndexValue.get(parent.getPatternInd()).add(currentPosition);
+            }
+
+            Node outputLink = parent.getOutputLink();
+            // Follow output links to find and record positions of other patterns
+            while (outputLink != null) {
+                // Add the current position to the list of positions for the pattern linked by outputLink
+                positionByStringIndexValue.get(outputLink.getPatternInd()).add(currentPosition);
+                outputLink = outputLink.getOutputLink();
+            }
+        }
+    }
+    // method to search for patterns in text
+    public static Map<String, ArrayList<Integer>> search(final String text, final String[] patterns) {
+        final var trie = new Trie(patterns);
+        final var positionByStringIndexValue = trie.searchIn(text);
+        return convert(positionByStringIndexValue, patterns);
+    }
+
+    // method for converting results to a map
+    private static Map<String, ArrayList<Integer>> convert(final ArrayList<ArrayList<Integer>> positionByStringIndexValue, final String[] patterns) {
+        Map<String, ArrayList<Integer>> positionByString = new HashMap<>();
+        for (int i = 0; i < patterns.length; i++) {
+            String pattern = patterns[i];
+            ArrayList<Integer> positions = positionByStringIndexValue.get(i);
+            positionByString.put(pattern, new ArrayList<>(positions));
+        }
+        return positionByString;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/strings/AhoCorasickTest.java b/src/test/java/com/thealgorithms/strings/AhoCorasickTest.java
new file mode 100644
index 00000000..caaca561
--- /dev/null
+++ b/src/test/java/com/thealgorithms/strings/AhoCorasickTest.java
@@ -0,0 +1,120 @@
+/*
+ * Tests For Aho-Corasick String Matching Algorithm
+ *
+ *            Author: Prabhat-Kumar-42
+ *    GitHub: https://github.com/Prabhat-Kumar-42
+ */
+
+package com.thealgorithms.strings;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Map;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+/**
+ * This class contains test cases for the Aho-Corasick String Matching Algorithm.
+ * The Aho-Corasick algorithm is used to efficiently find all occurrences of multiple
+ * patterns in a given text.
+ */
+class AhoCorasickTest {
+    private String[] patterns; // The array of patterns to search for
+    private String text; // The input text to search within
+
+    /**
+     * This method sets up the test environment before each test case.
+     * It initializes the patterns and text to be used for testing.
+     */
+    @BeforeEach
+    void setUp() {
+        patterns = new String[] {"ACC", "ATC", "CAT", "GCG", "C", "T"};
+        text = "GCATCG";
+    }
+
+    /**
+     * Test searching for multiple patterns in the input text.
+     * The expected results are defined for each pattern.
+     */
+    @Test
+    void testSearch() {
+        // Define the expected results for each pattern
+        final var expected = Map.of("ACC", new ArrayList<>(Arrays.asList()), "ATC", new ArrayList<>(Arrays.asList(2)), "CAT", new ArrayList<>(Arrays.asList(1)), "GCG", new ArrayList<>(Arrays.asList()), "C", new ArrayList<>(Arrays.asList(1, 4)), "T", new ArrayList<>(Arrays.asList(3)));
+        assertEquals(expected, AhoCorasick.search(text, patterns));
+    }
+
+    /**
+     * Test searching with an empty pattern array.
+     * The result should be an empty map.
+     */
+    @Test
+    void testEmptyPatterns() {
+        // Define an empty pattern array
+        final var emptyPatterns = new String[] {};
+        assertTrue(AhoCorasick.search(text, emptyPatterns).isEmpty());
+    }
+
+    /**
+     * Test searching for patterns that are not present in the input text.
+     * The result should be an empty list for each pattern.
+     */
+    @Test
+    void testPatternNotFound() {
+        // Define patterns that are not present in the text
+        final var searchPatterns = new String[] {"XYZ", "123"};
+        final var expected = Map.of("XYZ", new ArrayList<Integer>(), "123", new ArrayList<Integer>());
+        assertEquals(expected, AhoCorasick.search(text, searchPatterns));
+    }
+
+    /**
+     * Test searching for patterns that start at the beginning of the input text.
+     * The expected position for each pattern is 0.
+     */
+    @Test
+    void testPatternAtBeginning() {
+        // Define patterns that start at the beginning of the text
+        final var searchPatterns = new String[] {"GC", "GCA", "GCAT"};
+        final var expected = Map.of("GC", new ArrayList<Integer>(Arrays.asList(0)), "GCA", new ArrayList<Integer>(Arrays.asList(0)), "GCAT", new ArrayList<Integer>(Arrays.asList(0)));
+        assertEquals(expected, AhoCorasick.search(text, searchPatterns));
+    }
+
+    /**
+     * Test searching for patterns that end at the end of the input text.
+     * The expected positions are 4, 3, and 2 for the patterns.
+     */
+    @Test
+    void testPatternAtEnd() {
+        // Define patterns that end at the end of the text
+        final var searchPatterns = new String[] {"CG", "TCG", "ATCG"};
+        final var expected = Map.of("CG", new ArrayList<Integer>(Arrays.asList(4)), "TCG", new ArrayList<Integer>(Arrays.asList(3)), "ATCG", new ArrayList<Integer>(Arrays.asList(2)));
+        assertEquals(expected, AhoCorasick.search(text, searchPatterns));
+    }
+
+    /**
+     * Test searching for patterns with multiple occurrences in the input text.
+     * The expected sizes are 1 and 1, and the expected positions are 2 and 3
+     * for the patterns "AT" and "T" respectively.
+     */
+    @Test
+    void testMultipleOccurrencesOfPattern() {
+        // Define patterns with multiple occurrences in the text
+        final var searchPatterns = new String[] {"AT", "T"};
+        final var expected = Map.of("AT", new ArrayList<Integer>(Arrays.asList(2)), "T", new ArrayList<Integer>(Arrays.asList(3)));
+        assertEquals(expected, AhoCorasick.search(text, searchPatterns));
+    }
+
+    /**
+     * Test searching for patterns in a case-insensitive manner.
+     * The search should consider patterns regardless of their case.
+     */
+    @Test
+    void testCaseInsensitiveSearch() {
+        // Define patterns with different cases
+        final var searchPatterns = new String[] {"gca", "aTc", "C"};
+        final var expected = Map.of("gca", new ArrayList<Integer>(), "aTc", new ArrayList<Integer>(), "C", new ArrayList<Integer>(Arrays.asList(1, 4)));
+        assertEquals(expected, AhoCorasick.search(text, searchPatterns));
+    }
+}