Explorer
Data Structures & Algorithms

Implement polynomial rolling hash function for string pattern matching.

Problem Statement

Implement polynomial rolling hash of a lowercase string `s` with prime base `p` and modulo `m`. The hash formula is: `Hash(s) = (sum_{i=0}^{n-1} (s[i] - 'a' + 1) * p^i) % m`.

Examples

Input: s = "abc", p = 31, m = 1000000007

Output: 2946

Explanation: Combining the input according to Hashing In Strings | Theory logic yields 2946.

Input: s = "a", p = 31, m = 1000000007

Output: 1

Explanation: Combining the input according to Hashing In Strings | Theory logic yields 1.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: Polynomial rolling hash formula: sum_{i=0}^{n-1} (s[i] - "a" + 1) * p^i % m. šŸ’” Hint 2: Maintain running hash and power of p: pPow = (pPow * p) % m. šŸ’” Hint 3: Characters are 1-indexed: "a" = 1, "b" = 2, so s.charCodeAt(i) - 96.

Editorial & Approach

Problem Overview & Intuition

Polynomial rolling hash maps strings to integers. Using a prime base p (like 31 or 53) and a large prime modulo m (like 10^9 + 7), each character is weighted by p^i. This enables O(1) comparison of substrings.

Step-by-Step Approach

  1. Initialize hash = 0 and pPow = 1.
  2. Iterate i from 0 to s.length - 1.
  3. Value of character: val = s.charCodeAt(i) - 96.
  4. Accumulate: hash = (hash + val * pPow) % m.
  5. Advance power: pPow = (pPow * p) % m.
  6. Return hash.

Optimal Implementation (JavaScript)

function stringHash(s, p, m) {
  let hash = 0;
  let pPow = 1;
  for (let i = 0; i < s.length; i++) {
    hash = (hash + (s.charCodeAt(i) - 96) * pPow) % m;
    pPow = (pPow * p) % m;
  }
  return hash;
}

Complexity Analysis

Time Complexity O(N) ā€” single pass of string length N.
Space Complexity O(1) ā€” two integer variables.

Edge Cases & Corner Traps Handled

  • Single character "a": returns 1.
  • Large strings modulo m.

Hashing In Strings | Theory

Hard
Implement polynomial rolling hash of a lowercase string `s` with prime base `p` and modulo `m`. The hash formula is: `Hash(s) = (sum_{i=0}^{n-1} (s[i] - 'a' + 1) * p^i) % m`.
Example Scenarios
1Example 1
Input: s = "abc", p = 31, m = 1000000007
Output: 2946
Explanation:

Combining the input according to Hashing In Strings | Theory logic yields 2946.

2Example 2
Input: s = "a", p = 31, m = 1000000007
Output: 1
Explanation:

Combining the input according to Hashing In Strings | Theory logic yields 1.

Editor
Loading Editor...
s =
"abc"
p =
31
m =
1000000007
Output:Click "Run" above to execute and verify your code here.
2946