Leetcode Problem 2156. Find Substring With Given Hash Value

2156. Find Substring With Given Hash Value

Leetcode Solutions

Sliding Window + Rolling Hash

  1. Initialize cur to 0 and pk to 1 (which will represent p^k modulo m).
  2. Traverse the string s from the end to the beginning.
  3. Update cur to be the rolling hash of the current window of size k.
  4. If the window size is less than k, multiply pk by p modulo m.
  5. If the window size is at least k, subtract the contribution of the character that is leaving the window, making sure to add m before taking modulo to avoid negative values.
  6. If cur equals hashValue, store the current starting index of the substring.
  7. After the loop, return the substring starting from the stored index with length k.
UML Thumbnail

Brute Force Substring Hashing

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...