Skip to content

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 hashed = 0;
    int bestLeft = -1;

    auto val = [](char c) -> int { return c - 'a' + 1; };

    for (int i = s.length() - 1; i >= 0; --i) {
      hashed = (hashed * power + val(s[i])) % modulo;
      if (i + k < s.length())
        hashed = (hashed - val(s[i + k]) * maxPower % modulo + modulo) % modulo;
      else
        maxPower = maxPower * power % modulo;
      if (hashed == 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 hashed = 0;
    int bestLeft = -1;

    for (int i = s.length() - 1; i >= 0; --i) {
      hashed = (hashed * power + val(s.charAt(i))) % modulo;
      if (i + k < s.length())
        hashed = (hashed - val(s.charAt(i + k)) * maxPower % modulo + modulo) % modulo;
      else
        maxPower = maxPower * power % modulo;
      if (hashed == 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)
    hashed = 0

    def val(c: chr) -> int:
      return ord(c) - ord('a') + 1

    for i, c in reversed(list(enumerate(s))):
      hashed = (hashed * power + val(c)) % modulo
      if i + k < len(s):
        hashed = (hashed - val(s[i + k]) * maxPower) % modulo
      if hashed == hashValue:
        bestLeft = i

    return s[bestLeft:bestLeft + k]