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 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]