TheAlgorithms/Java

[FEATURE REQUEST] Rabin Karp String Algorithm

pankaj-bind opened this issue · 5 comments

pankaj-bind commented

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.

pankaj-bind commented

please assign me this task

  • 👍1
vil02 commented

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?

pankaj-bind commented

ok

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?