Given strings and substring-related queries, use rolling hash to efficiently solve common string problems. The goal is to avoid repeatedly comparing long substrings character by character. Instead, compute prefix hashes once and use them to compare substrings quickly. For this article, the code will support three important rolling hash applications:
Find all occurrences of a pattern in a text
Check whether two substrings are equal
Find the longest duplicate substring
Example 1
Input: text = "ababcabcab"pattern = "abc"
Output: [2, 5]
Explanation: The pattern "abc" appears in the text starting at index 2 and index 5.
Example 2
Input: s = "banana"
Output: "ana"
Explanation: The substring "ana" appears twice in "banana": once starting at index 1 and once starting at index 3.
Approach
A normal substring comparison checks characters one by one. If the substring length is large, this becomes slow, especially when many comparisons are needed. Rolling hash gives every prefix of the string a numeric value. Once prefix hashes are ready, the hash of any substring can be extracted by removing the contribution of the prefix before it.
Think of a string like a number written in a special base: hash("abc") = a * base^2 + b * base + c If the hash of s[0...r] is known and the hash of s[0...l-1] is known, the substring s[l...r] can be separated using powers of the base. The important observation is: Equal substrings always have equal hashes.
Different substrings may rarely have the same hash, called a collision. That is why the code uses double hashing and also verifies actual strings when a final match matters.
Algorithm
Choose two large prime mod values and one base. Two mod values reduce the chance of hash collision.
Build prefix hash arrays for the string. This is done so any substring hash can be extracted quickly later.
Build power arrays for the base. These powers are needed to remove the left prefix correctly when calculating a substring hash.
To compare two substrings, calculate both substring hashes. If the hashes differ, the substrings are definitely different.
If hashes match in a place where correctness matters, verify the actual characters. This protects the solution from rare hash collisions.
For longest duplicate substring, binary search on the length. If a duplicate of length
Lexists, then smaller duplicate lengths are also possible, so binary search works naturally.
Dry Run
Introduction to Rolling Hash
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: static const long long MOD1 = 1000000007LL; static const long long MOD2 = 1000000009LL; static const long long BASE = 911382LL; /* Stores prefix hashes and base powers so substring hashes can be calculated in constant time. */ struct RollingHash { vector<long long> hash1; vector<long long> hash2; vector<long long> power1; vector<long long> power2; /* Builds prefix hashes and powers for the given string. */ RollingHash(const string& s) { int n = s.size(); // Prefix hash arrays store hash values up to each index. hash1.assign(n + 1, 0); hash2.assign(n + 1, 0); // Power arrays store base powers needed for substring hashes. power1.assign(n + 1, 1); power2.assign(n + 1, 1); for (int i = 0; i < n; i++) { int value = (int)s[i]; hash1[i + 1] = (hash1[i] * BASE + value) % MOD1; hash2[i + 1] = (hash2[i] * BASE + value) % MOD2; power1[i + 1] = (power1[i] * BASE) % MOD1; power2[i + 1] = (power2[i] * BASE) % MOD2; } } /* Returns the double hash of substring [left, right). */ pair<long long, long long> getHash(int left, int right) { long long x1 = (hash1[right] - (hash1[left] * power1[right - left]) % MOD1); long long x2 = (hash2[right] - (hash2[left] * power2[right - left]) % MOD2); // The subtraction can become negative after removing the prefix. if (x1 < 0) { x1 += MOD1; } // The second hash needs the same negative-value fix. if (x2 < 0) { x2 += MOD2; } return {x1, x2}; } }; /* Finds a duplicate substring start for a fixed length. */ int duplicateStartForLength(const string& s, int length, RollingHash& rh) { // Length 0 is always valid but not useful as an answer. if (length == 0) { return 0; } unordered_map<unsigned long long, vector<int>> seen; int n = s.size(); for (int i = 0; i + length <= n; i++) { auto currentHash = rh.getHash(i, i + length); unsigned long long key = ((unsigned long long)currentHash.first << 32) ^ (unsigned long long)currentHash.second; // A repeated hash may mean a real duplicate or a rare collision. if (seen.find(key) != seen.end()) { for (int previous : seen[key]) { // Exact comparison confirms the duplicate safely. if (s.compare(previous, length, s, i, length) == 0) { return i; } } } seen[key].push_back(i); } return -1; }public: /* Finds all starting indices where pattern appears in text. */ vector<int> findPatternOccurrences(string text, string pattern) { vector<int> result; // Empty or longer patterns cannot produce normal matches here. if (pattern.empty() || pattern.size() > text.size()) { return result; } RollingHash textHash(text); RollingHash patternHash(pattern); int n = text.size(); int m = pattern.size(); auto targetHash = patternHash.getHash(0, m);Complexity Analysis
For pattern matching, preprocessing takes O(n + m) time and scanning takes O(n) expected time. Space complexity is O(n + m).
For substring equality, preprocessing takes O(n) time. Each hash comparison takes O(1) time after preprocessing. Space complexity is O(n).
For longest duplicate substring, binary search tries O(log n) lengths, and each length is checked in O(n) expected time. So the time complexity is O(n log n). Space complexity is O(n).
Interview follow-up Questions
A single hash can rarely collide for different substrings. Double hashing compares two separate hash values, making accidental matches much less likely.
Be the first to add a comment.