-
Notifications
You must be signed in to change notification settings - Fork 18.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[FEATURE REQUEST] Rabin Karp String Algorithm #5136
Comments
please assign me this task |
There are two existing implementations of this algorithms:
Would you like to create a PR in which you remove one of them, test and cleanup the other one? |
ok
|
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution! |
Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution! |
What would you like to Propose?
The Rabin-Karp algorithm is a string searching algorithm that searches for a pattern within a text using hashing. It's particularly efficient for searching multiple patterns in the same text, as it preprocesses the patterns into hash values and then efficiently compares these hash values with those of substrings in the text.
Issue details
Missing Implementation: The Rabin-Karp string search algorithm needs to be implemented in the codebase.
Efficiency Concerns: Ensure that the algorithm is implemented efficiently, particularly regarding hash computation and collision handling.
Testing: Comprehensive testing should be conducted to ensure the correctness and efficiency of the implementation. This includes testing edge cases, such as empty strings and patterns, as well as performance testing for large inputs.
Additional Information
Algorithm Description:
Preprocessing: Compute the hash value of the pattern and the first window of the text using a rolling hash function.
Search: Slide the window across the text, computing the hash value of each subsequent window in constant time using the rolling hash function. Compare these hash values with the hash value of the pattern. If they match, perform a full comparison of the pattern and the substring to confirm the match.
Handling Collisions: To handle hash collisions, compare the substrings character by character if the hash values match.
The text was updated successfully, but these errors were encountered: