Rabin Karp in C and Java

[Kumar-laxmi]

Problem = Rabin- Karp:

The Rabin-Karp algorithm is a string matching algorithm used to find occurrences of a pattern string within a larger text string. Given a pattern string and a text string, the algorithm determines if the pattern occurs within the text and returns the starting indices of all occurrences.

Approach :

1. Preprocessing:

   • Calculate the hash value of the pattern.
   • Calculate the hash values of all substrings of the text that have the same length as the pattern.

2. Matching:

   • Compare the hash value of the pattern with the hash values of all substrings of the text.
   • If a match is found, perform a full string comparison to verify if the pattern truly matches the substring.
   • If the pattern matches the substring, record the starting index as a potential occurrence.

3. Rolling Hash: -Use a rolling hash technique to efficiently calculate the hash value of subsequent substrings. -Update the hash value by subtracting the contribution of the first character and adding the contribution of the next character as -the window slides over the text.

4. Hash Function:

   • Use a hash function that treats the characters of the string as coefficients of a polynomial and evaluates the polynomial using a fixed base.
   • Calculate the hash value using the Horner's rule, which reduces the time complexity of evaluating the polynomial.

5. Efficiency:

   • The algorithm avoids unnecessary character-by-character comparisons by comparing hash values.
   • It has an average time complexity of O(N + M), where N is the length of the text and M is the length of the pattern.
   • The choice of a good hash function and a proper base value is crucial to minimize collisions and improve performance

Feature to be Added

• This is already implemented in C++ and Python but missing in C and Java.

[Inferno2211]

Could you please assign this to me under SSOC'23?

[shanvijha30]

@Kumar-laxmi I would like to work on this issue. Please assign it to me. Thank you!

[neerajrpatil]

@Kumar-laxmi Input: Text: "AABAACAADAABAABA" Pattern: "AABA"

Output: Occurrences found at indices: [0, 9, 12] I am familiar with Rabin- Karp: algorithm , I would like to solve this issue..

[kundu-baivab]

Please assign this issue to me. I would be able to solve this problem in both C and JAVA languages.

[Kumar-laxmi]

Assigned! @kundu-baivab : C & Java

[Swapnendu003]

I have submitted the code in C and JAVA already