feat: Add Aho-Corasick multi-pattern search implementation and unit tests#7518
Open
priyanshuvishwakarma273403 wants to merge 1 commit into
Open
Conversation
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## master #7518 +/- ##
============================================
+ Coverage 79.85% 80.24% +0.39%
- Complexity 7328 7376 +48
============================================
Files 807 811 +4
Lines 23817 23863 +46
Branches 4687 4694 +7
============================================
+ Hits 19018 19150 +132
+ Misses 4036 3949 -87
- Partials 763 764 +1 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
Contributor
Author
|
@DenizAltunkapan broh kindly check this pr |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This PR implements the Aho-Corasick string matching algorithm under the com.thealgorithms.searches package.
The Aho-Corasick algorithm is a multi-pattern matching algorithm that efficiently finds all occurrences of a set of pattern strings within an input text in a single pass. It is particularly useful when searching for a large dictionary of keywords (e.g., in virus signatures, spam filters, or keyword matching).
Implementation Details$O(m)$ time, where $m$ is the total length of all patterns.$O(1)$ lookup per match.$O(n + z)$ time, where $n$ is the length of the text and $z$ is the number of matched occurrences.$O(n + m + z)$ where:
$n$ is the length of the input text.
$m$ is the total length of all pattern strings.
$z$ is the number of matches found.$O(m)$ to store the Trie state transitions.
Trie Construction: Inserts all input patterns into a Trie (keyword tree) in
Failure and Output Links: Computes failure transitions and output shortcuts using a Breadth-First Search (BFS) traversal.
A failure link points to the node representing the longest proper suffix of the current prefix that is also a prefix of some pattern.
An output link shortcuts to the next node in the failure chain that represents a complete pattern match, ensuring
Search Traversal: Scans the input text once in
Complexity
Time Complexity:
Space Complexity:
Example Behavior
For the input:
Text: ahishers
Patterns: ["he", "she", "his", "hers"]
The output matches:
his at index 1
she at index 3
he at index 4
hers at index 4
Testing
Comprehensive unit tests have been added under com.thealgorithms.searches.AhoCorasickSearchTest covering:
Basic search with overlapping matches (as described above)
Edge cases (null/empty text, null/empty pattern list)
Inputs with no matching patterns
Complex overlapping duplicates (e.g. text "aaaa" with patterns ["a", "aa", "aaa", "aaaa"])