Rabin-Karp Algorithm:

The Rabin-Karp algorithm is a string matching algorithm that uses hashing to efficiently find occurrences of a pattern within a text. It employs a rolling hash function to reduce the number of character comparisons during pattern matching.

Algorithm Steps:

1.    Initialization:

·        Compute the hash value of the pattern and the first substring of the text.

2.    Comparison:

·        If the hash values match, perform a character-by-character comparison to confirm the match.

3.    Rolling Hash:

·        Move to the next substring in the text by updating the hash value based on the previous hash and the new character.

4.    Repeat:

·        Continue steps 2-3 until the end of the text is reached.

5.    Pattern Match:

·        If a match is found, record the position or perform the required action.

6.    Shift the Pattern:

·        Move the pattern to the next position and repeat the process.

Example:

Consider the text: "ABABCABABABCABABABC" and the pattern: "ABAB".

Algorithm Execution:

1.    Initialization:

·        Compute the hash value of the pattern "ABAB" and the first substring "ABAB" in the text.

2.    Comparison:

·        Hash values match, so perform a character-by-character comparison to confirm the match.

3.    Rolling Hash:

·        Move to the next substring "BABC" in the text by updating the hash value based on the previous hash and the new character "C".

4.    Repeat:

·        Continue the process until the end of the text.

5.    Pattern Match:

·        At positions 2, 7, and 12, the pattern "ABAB" matches substrings in the text.

Result:

  • Matches found at positions 2, 7, and 12 in the text.

Advantages:

  • Efficient for large texts as it reduces the number of character comparisons.
  • Rolling hash allows for constant-time updates of the hash value.

Note:

  • Rabin-Karp uses modular arithmetic to handle hash value updates and avoid integer overflow.
  • It is particularly useful when multiple patterns need to be searched simultaneously in the same text.