What would you like to share?
What would you like to Propose?
Add an implementation of the Aho-Corasick string matching algorithm.
Problem statement: Given a text and a list of patterns, find all occurrences of all patterns in the text efficiently. This algorithm is useful when multiple keywords need to be searched in a single pass.
Issue details
The implementation can be added under the string/search-related package and should include unit tests.
Expected behavior examples:
Input:
- text:
ahishers
- patterns:
["he", "she", "his", "hers"]
Expected matches:
his at index 1she at index 3he at index 4hers at index 4
Suggested implementation details:
- Build a trie from all patterns.
- Compute failure links using BFS.
- Traverse the input text once and report matched patterns.
- Expected time complexity:
O(n + m + z), where n is the text length, m is the total length of all patterns, and z is the number of matches.
- Expected space complexity:
O(m).
Additional Information
This would be a useful addition for educational coverage of multi-pattern string matching algorithms.
Additional information
No response
What would you like to share?
What would you like to Propose?
Add an implementation of the Aho-Corasick string matching algorithm.
Problem statement: Given a text and a list of patterns, find all occurrences of all patterns in the text efficiently. This algorithm is useful when multiple keywords need to be searched in a single pass.
Issue details
The implementation can be added under the string/search-related package and should include unit tests.
Expected behavior examples:
Input:
ahishers["he", "she", "his", "hers"]Expected matches:
hisat index1sheat index3heat index4hersat index4Suggested implementation details:
O(n + m + z), wherenis the text length,mis the total length of all patterns, andzis the number of matches.O(m).Additional Information
This would be a useful addition for educational coverage of multi-pattern string matching algorithms.
Additional information
No response