Rabin-Karp Substring Search Implementation

By Siddesh Patankar

This C++ project showcases the Rabin-Karp algorithm, a quick and efficient method for text pattern matching using hashing.

The provided C++ code is an implementation of the Rabin-Karp algorithm, a popular string-searching algorithm. This algorithm efficiently locates a pattern within a given text or string.

Here's how the code works:

1. It starts by reading two input strings, 's' and 'p', representing the text and pattern to be searched, respectively.

2. It calculates hash values for both the pattern and the first window of the text. Hash values are computed using modulo arithmetic to avoid overflow.

3. The code then iterates through the text in a sliding window fashion, comparing the hash value of the current window with the hash value of the pattern. If they match, it performs a character-wise comparison to verify if the pattern truly exists in that position.

4. If a match is found, the code prints the position where the pattern is located in the text.

5. The algorithm continues sliding the window through the text until the entire text is searched.

6. If the pattern length is greater than or equal to the text length, the code reports it as an invalid pattern.

The Rabin-Karp algorithm is known for its ability to search for patterns efficiently, especially in situations where other algorithms like the naive substring search would be less performant. It achieves this by using hashing to compare substrings quickly. This code is a practical implementation of the Rabin-Karp algorithm, demonstrating its effectiveness in pattern-matching tasks.