Skip to content

feat: Add Aho-Corasick multi-pattern search implementation and unit tests#7518

Open
priyanshuvishwakarma273403 wants to merge 1 commit into
TheAlgorithms:masterfrom
priyanshuvishwakarma273403:feat-7442-aho-corasick
Open

feat: Add Aho-Corasick multi-pattern search implementation and unit tests#7518
priyanshuvishwakarma273403 wants to merge 1 commit into
TheAlgorithms:masterfrom
priyanshuvishwakarma273403:feat-7442-aho-corasick

Conversation

@priyanshuvishwakarma273403

Copy link
Copy Markdown
Contributor

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
Trie Construction: Inserts all input patterns into a Trie (keyword tree) in $O(m)$ time, where $m$ is the total length of all patterns.
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 $O(1)$ lookup per match.
Search Traversal: Scans the input text once in $O(n + z)$ time, where $n$ is the length of the text and $z$ is the number of matched occurrences.
Complexity
Time Complexity: $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.
Space Complexity: $O(m)$ to store the Trie state transitions.
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"])

@codecov-commenter

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 82.89474% with 13 lines in your changes missing coverage. Please review.
✅ Project coverage is 80.24%. Comparing base (8a3bd3a) to head (2779272).
⚠️ Report is 20 commits behind head on master.

Files with missing lines Patch % Lines
.../com/thealgorithms/searches/AhoCorasickSearch.java 82.89% 9 Missing and 4 partials ⚠️
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.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

@priyanshuvishwakarma273403

Copy link
Copy Markdown
Contributor Author

@DenizAltunkapan broh kindly check this pr
thank you

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants