30-seconds-of-java icon indicating copy to clipboard operation
30-seconds-of-java copied to clipboard

Implement Rabin-Karp algorithm for substring search

Open nayan458 opened this issue 3 months ago • 2 comments

Summary

This PR introduces the Rabin-Karp algorithm for substring search in Java. It includes:

  • RabinKarpSubstringSearchSnippet class with:
    • rabinKarpSearch method to find the first occurrence of a substring.
    • Efficient hash computation using a large prime.
    • Sliding window hash recalculation.
    • Substring equality check for collision handling.
  • RabinKarpSubstringSearchSnippetTest class similar to the tests in KMP for testing and comparisons.
  • A ready-to-use README.md snippet documenting usage.
  • BUILD SUCCESSFUL

Benefits

  • Provides an alternative to KMP for substring search.
  • Suitable for multiple pattern searches with rolling hash.
  • Modular, clean, and well-documented code for educational and production use.

Notes

  • Uses 1_000_000_007 as prime to reduce hash collisions.
  • Designed for clarity and maintainability.

nayan458 avatar Oct 01 '25 18:10 nayan458