# 2156. Find Substring With Given Hash Value¶

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: string subStrHash(string s, int power, int modulo, int k, int hashValue) { long maxPower = 1; long hash = 0; int bestLeft = -1; auto val = [](char c) -> int { return c - 'a' + 1; }; for (int i = s.length() - 1; i >= 0; --i) { hash = (hash * power + val(s[i])) % modulo; if (i + k < s.length()) hash = (hash - val(s[i + k]) * maxPower % modulo + modulo) % modulo; else maxPower = maxPower * power % modulo; if (hash == hashValue) bestLeft = i; } return s.substr(bestLeft, k); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public String subStrHash(String s, int power, int modulo, int k, int hashValue) { long maxPower = 1; long hash = 0; int bestLeft = -1; for (int i = s.length() - 1; i >= 0; --i) { hash = (hash * power + val(s.charAt(i))) % modulo; if (i + k < s.length()) hash = (hash - val(s.charAt(i + k)) * maxPower % modulo + modulo) % modulo; else maxPower = maxPower * power % modulo; if (hash == hashValue) bestLeft = i; } return s.substring(bestLeft, bestLeft + k); } private int val(char c) { return c - 'a' + 1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str: maxPower = pow(power, k, modulo) hash = 0 def val(c: str) -> int: return ord(c) - ord('a') + 1 for i, c in reversed(list(enumerate(s))): hash = (hash * power + val(c)) % modulo if i + k < len(s): hash = (hash - val(s[i + k]) * maxPower) % modulo if hash == hashValue: bestLeft = i return s[bestLeft:bestLeft + k]