Polynomial Rolling Hash Code Implementations
Complete Polynomial Rolling Hash code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Polynomial Rolling Hash Guide · Launch Interactive Visualizer
C++ Implementation
// Rolling Hash Implementation in C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <chrono>
class RollingHash {
private:
int base;
int mod;
std::vector<int> powers;
public:
RollingHash(int base = 256, int mod = 1000000007) : base(base), mod(mod) {
powers.push_back(1);
}
// Precompute powers of base
void precomputePowers(int maxLength) {
while (powers.size() <= maxLength) {
powers.push_back((long long)powers.back() * base % mod);
}
}
// Compute hash of a string
int hash(const std::string& str) {
int hash = 0;
for (char c : str) {
hash = ((long long)hash * base + c) % mod;
}
return hash;
}
// Compute rolling hash for all substrings of given length
std::vector<int> rollingHash(const std::string& str, int length) {
if (str.length() < length) return {};
precomputePowers(length);
std::vector<int> hashes;
int currentHash = 0;
// Compute hash for first substring
for (int i = 0; i < length; i++) {
currentHash = ((long long)currentHash * base + str[i]) % mod;
}
hashes.push_back(currentHash);
// Compute rolling hash for remaining substrings
for (int i = length; i < str.length(); i++) {
currentHash = (((long long)(currentHash - str[i - length] * powers[length - 1]) * base + str[i]) % mod);
if (currentHash < 0) currentHash += mod;
hashes.push_back(currentHash);
}
return hashes;
}
// Find all occurrences of pattern in text
std::vector<int> findPattern(const std::string& text, const std::string& pattern) {
int patternHash = hash(pattern);
std::vector<int> textHashes = rollingHash(text, pattern.length());
std::vector<int> matches;
for (int i = 0; i < textHashes.size(); i++) {
if (textHashes[i] == patternHash) {
// Verify match (handle hash collisions)
if (text.substr(i, pattern.length()) == pattern) {
matches.push_back(i);
}
}
}
return matches;
}
// Find longest common substring
std::string findLongestCommonSubstring(const std::string& str1, const std::string& str2) {
int maxLength = 0;
int maxStart = 0;
for (int length = std::min(str1.length(), str2.length()); length > 0; length--) {
std::unordered_set<int> hashes1;
auto hashes = rollingHash(str1, length);
hashes1.insert(hashes.begin(), hashes.end());
std::vector<int> hashes2 = rollingHash(str2, length);
for (int i = 0; i < hashes2.size(); i++) {
if (hashes1.find(hashes2[i]) != hashes1.end()) {
// Verify match
std::string substring = str2.substr(i, length);
if (str1.find(substring) != std::string::npos) {
maxLength = length;
maxStart = i;
break;
}
}
}
if (maxLength > 0) break;
}
return maxLength > 0 ? str2.substr(maxStart, maxLength) : "";
}
// Find repeated substrings
std::vector<std::string> findRepeatedSubstrings(const std::string& str, int minLength = 2) {
std::vector<std::string> repeated;
for (int length = minLength; length <= str.length() / 2; length++) {
std::vector<int> hashes = rollingHash(str, length);
std::unordered_map<int, std::vector<std::string>> hashCount;
for (int i = 0; i < hashes.size(); i++) {
int hash = hashes[i];
std::string substring = str.substr(i, length);
hashCount[hash].push_back(substring);
}
for (const auto& pair : hashCount) {
if (pair.second.size() > 1) {
repeated.push_back(pair.second[0]);
}
}
}
return repeated;
}
// Check if two strings are equal using rolling hash
bool areEqual(const std::string& str1, const std::string& str2) {
if (str1.length() != str2.length()) return false;
return hash(str1) == hash(str2);
}
// Performance measurement
struct RollingHashResult {
std::vector<int> matches;
int count;
long long executionTime;
RollingHashResult(const std::vector<int>& m, int c, long long t)
: matches(m), count(c), executionTime(t) {}
};
RollingHashResult measurePerformance(const std::string& text, const std::string& pattern) {
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> matches = findPattern(text, pattern);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
return RollingHashResult(matches, matches.size(), duration.count());
}
// Performance comparison
static void comparePerformance(const std::string& text, const std::string& pattern) {
auto start = std::chrono::high_resolution_clock::now();
RollingHash rh;
std::vector<int> matches = rh.findPattern(text, pattern);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Rolling Hash Search: " << matches.size() << " matches found in "
<< duration.count() << " μs" << std::endl;
}
};JAVA Implementation
// Rolling Hash Implementation in Java
import java.util.*;
public class RollingHash {
private final int base;
private final int mod;
private final List<Integer> powers;
public RollingHash(int base, int mod) {
this.base = base;
this.mod = mod;
this.powers = new ArrayList<>();
this.powers.add(1);
}
public RollingHash() {
this(256, 1000000007);
}
// Precompute powers of base
private void precomputePowers(int maxLength) {
while (powers.size() <= maxLength) {
powers.add((int) ((long) powers.get(powers.size() - 1) * base % mod));
}
}
// Compute hash of a string
public int hash(String str) {
int hash = 0;
for (char c : str.toCharArray()) {
hash = (int) ((long) hash * base + c) % mod;
}
return hash;
}
// Compute rolling hash for all substrings of given length
public List<Integer> rollingHash(String str, int length) {
if (str.length() < length) return new ArrayList<>();
precomputePowers(length);
List<Integer> hashes = new ArrayList<>();
int currentHash = 0;
// Compute hash for first substring
for (int i = 0; i < length; i++) {
currentHash = (int) ((long) currentHash * base + str.charAt(i)) % mod;
}
hashes.add(currentHash);
// Compute rolling hash for remaining substrings
for (int i = length; i < str.length(); i++) {
currentHash = (int) (((long) (currentHash - str.charAt(i - length) * powers.get(length - 1)) * base + str.charAt(i)) % mod);
if (currentHash < 0) currentHash += mod;
hashes.add(currentHash);
}
return hashes;
}
// Find all occurrences of pattern in text
public List<Integer> findPattern(String text, String pattern) {
int patternHash = hash(pattern);
List<Integer> textHashes = rollingHash(text, pattern.length());
List<Integer> matches = new ArrayList<>();
for (int i = 0; i < textHashes.size(); i++) {
if (textHashes.get(i) == patternHash) {
// Verify match (handle hash collisions)
if (text.substring(i, i + pattern.length()).equals(pattern)) {
matches.add(i);
}
}
}
return matches;
}
// Find longest common substring
public String findLongestCommonSubstring(String str1, String str2) {
int maxLength = 0;
int maxStart = 0;
for (int length = Math.min(str1.length(), str2.length()); length > 0; length--) {
Set<Integer> hashes1 = new HashSet<>(rollingHash(str1, length));
List<Integer> hashes2 = rollingHash(str2, length);
for (int i = 0; i < hashes2.size(); i++) {
if (hashes1.contains(hashes2.get(i))) {
// Verify match
String substring = str2.substring(i, i + length);
if (str1.contains(substring)) {
maxLength = length;
maxStart = i;
break;
}
}
}
if (maxLength > 0) break;
}
return maxLength > 0 ? str2.substring(maxStart, maxStart + maxLength) : "";
}
// Find repeated substrings
public Set<String> findRepeatedSubstrings(String str, int minLength) {
Set<String> repeated = new HashSet<>();
for (int length = minLength; length <= str.length() / 2; length++) {
List<Integer> hashes = rollingHash(str, length);
Map<Integer, List<String>> hashCount = new HashMap<>();
for (int i = 0; i < hashes.size(); i++) {
int hash = hashes.get(i);
String substring = str.substring(i, i + length);
hashCount.computeIfAbsent(hash, k -> new ArrayList<>()).add(substring);
}
for (List<String> substrings : hashCount.values()) {
if (substrings.size() > 1) {
repeated.add(substrings.get(0));
}
}
}
return repeated;
}
// Check if two strings are equal using rolling hash
public boolean areEqual(String str1, String str2) {
if (str1.length() != str2.length()) return false;
return hash(str1) == hash(str2);
}
// Performance measurement
public static class RollingHashResult {
public List<Integer> matches;
public int count;
public long executionTime;
public RollingHashResult(List<Integer> matches, int count, long executionTime) {
this.matches = matches;
this.count = count;
this.executionTime = executionTime;
}
}
public RollingHashResult measurePerformance(String text, String pattern) {
long startTime = System.nanoTime();
List<Integer> matches = findPattern(text, pattern);
long endTime = System.nanoTime();
return new RollingHashResult(matches, matches.size(), endTime - startTime);
}
// Utility methods
public static RollingHash create(int base, int mod) {
return new RollingHash(base, mod);
}
public static List<Integer> findPatternWithRollingHash(String text, String pattern, int base, int mod) {
RollingHash rh = new RollingHash(base, mod);
return rh.findPattern(text, pattern);
}
public static String findLongestCommonSubstringWithRollingHash(String str1, String str2, int base, int mod) {
RollingHash rh = new RollingHash(base, mod);
return rh.findLongestCommonSubstring(str1, str2);
}
}JAVASCRIPT Implementation
// Rolling Hash Implementation in JavaScript
class RollingHash {
constructor(base = 256, mod = 1000000007) {
this.base = base;
this.mod = mod;
this.powers = [1];
}
// Precompute powers of base
precomputePowers(maxLength) {
while (this.powers.length <= maxLength) {
this.powers.push((this.powers[this.powers.length - 1] * this.base) % this.mod);
}
}
// Compute hash of a string
hash(str) {
let hash = 0;
for (let i = 0; i < str.length; i++) {
hash = (hash * this.base + str.charCodeAt(i)) % this.mod;
}
return hash;
}
// Compute rolling hash for all substrings of given length
rollingHash(str, length) {
if (str.length < length) return [];
this.precomputePowers(length);
const hashes = [];
let currentHash = 0;
// Compute hash for first substring
for (let i = 0; i < length; i++) {
currentHash = (currentHash * this.base + str.charCodeAt(i)) % this.mod;
}
hashes.push(currentHash);
// Compute rolling hash for remaining substrings
for (let i = length; i < str.length; i++) {
currentHash = ((currentHash - str.charCodeAt(i - length) * this.powers[length - 1]) * this.base + str.charCodeAt(i)) % this.mod;
if (currentHash < 0) currentHash += this.mod;
hashes.push(currentHash);
}
return hashes;
}
// Find all occurrences of pattern in text
findPattern(text, pattern) {
const patternHash = this.hash(pattern);
const textHashes = this.rollingHash(text, pattern.length);
const matches = [];
for (let i = 0; i < textHashes.length; i++) {
if (textHashes[i] === patternHash) {
// Verify match (handle hash collisions)
if (text.substring(i, i + pattern.length) === pattern) {
matches.push(i);
}
}
}
return matches;
}
// Find longest common substring
findLongestCommonSubstring(str1, str2) {
let maxLength = 0;
let maxStart = 0;
for (let len = Math.min(str1.length, str2.length); len > 0; len--) {
const hashes1 = new Set(this.rollingHash(str1, len));
const hashes2 = this.rollingHash(str2, len);
for (let i = 0; i < hashes2.length; i++) {
if (hashes1.has(hashes2[i])) {
// Verify match
const substring = str2.substring(i, i + len);
if (str1.includes(substring)) {
maxLength = len;
maxStart = i;
break;
}
}
}
if (maxLength > 0) break;
}
return maxLength > 0 ? str2.substring(maxStart, maxStart + maxLength) : "";
}
// Find repeated substrings
findRepeatedSubstrings(str, minLength = 2) {
const repeated = new Set();
for (let len = minLength; len <= str.length / 2; len++) {
const hashes = this.rollingHash(str, len);
const hashCount = new Map();
for (let i = 0; i < hashes.length; i++) {
const hash = hashes[i];
const substring = str.substring(i, i + len);
if (!hashCount.has(hash)) {
hashCount.set(hash, []);
}
hashCount.get(hash).push(substring);
}
for (const [hash, substrings] of hashCount) {
if (substrings.length > 1) {
repeated.add(substrings[0]);
}
}
}
return Array.from(repeated);
}
// Check if two strings are equal using rolling hash
areEqual(str1, str2) {
if (str1.length !== str2.length) return false;
return this.hash(str1) === this.hash(str2);
}
// Find palindromes using rolling hash
findPalindromes(str) {
const palindromes = [];
for (let i = 0; i < str.length; i++) {
// Check odd length palindromes
let left = i, right = i;
while (left >= 0 && right < str.length && str[left] === str[right]) {
if (right - left + 1 > 1) {
palindromes.push(str.substring(left, right + 1));
}
left--;
right++;
}
// Check even length palindromes
left = i;
right = i + 1;
while (left >= 0 && right < str.length && str[left] === str[right]) {
palindromes.push(str.substring(left, right + 1));
left--;
right++;
}
}
return palindromes;
}
// Performance measurement
measurePerformance(text, pattern) {
const startTime = performance.now();
const matches = this.findPattern(text, pattern);
const endTime = performance.now();
return {
matches,
count: matches.length,
executionTime: endTime - startTime
};
}
}
// Utility functions
function createRollingHash(base = 256, mod = 1000000007) {
return new RollingHash(base, mod);
}
function findPatternWithRollingHash(text, pattern, base = 256, mod = 1000000007) {
const rh = new RollingHash(base, mod);
return rh.findPattern(text, pattern);
}
function findLongestCommonSubstringWithRollingHash(str1, str2, base = 256, mod = 1000000007) {
const rh = new RollingHash(base, mod);
return rh.findLongestCommonSubstring(str1, str2);
}
function findRepeatedSubstringsWithRollingHash(str, minLength = 2, base = 256, mod = 1000000007) {
const rh = new RollingHash(base, mod);
return rh.findRepeatedSubstrings(str, minLength);
}PYTHON Implementation
# Rolling Hash Implementation in Python
class RollingHash:
def __init__(self, base=256, mod=1000000007):
self.base = base
self.mod = mod
self.powers = [1]
def precompute_powers(self, max_length):
"""Precompute powers of base"""
while len(self.powers) <= max_length:
self.powers.append((self.powers[-1] * self.base) % self.mod)
def hash(self, s):
"""Compute hash of a string"""
hash_val = 0
for c in s:
hash_val = (hash_val * self.base + ord(c)) % self.mod
return hash_val
def rolling_hash(self, s, length):
"""Compute rolling hash for all substrings of given length"""
if len(s) < length:
return []
self.precompute_powers(length)
hashes = []
current_hash = 0
# Compute hash for first substring
for i in range(length):
current_hash = (current_hash * self.base + ord(s[i])) % self.mod
hashes.append(current_hash)
# Compute rolling hash for remaining substrings
for i in range(length, len(s)):
current_hash = ((current_hash - ord(s[i - length]) * self.powers[length - 1]) * self.base + ord(s[i])) % self.mod
if current_hash < 0:
current_hash += self.mod
hashes.append(current_hash)
return hashes
def find_pattern(self, text, pattern):
"""Find all occurrences of pattern in text"""
pattern_hash = self.hash(pattern)
text_hashes = self.rolling_hash(text, len(pattern))
matches = []
for i, text_hash in enumerate(text_hashes):
if text_hash == pattern_hash:
# Verify match (handle hash collisions)
if text[i:i + len(pattern)] == pattern:
matches.append(i)
return matches
def find_longest_common_substring(self, str1, str2):
"""Find longest common substring"""
max_length = 0
max_start = 0
for length in range(min(len(str1), len(str2)), 0, -1):
hashes1 = set(self.rolling_hash(str1, length))
hashes2 = self.rolling_hash(str2, length)
for i, hash_val in enumerate(hashes2):
if hash_val in hashes1:
# Verify match
substring = str2[i:i + length]
if substring in str1:
max_length = length
max_start = i
break
if max_length > 0:
break
return str2[max_start:max_start + max_length] if max_length > 0 else ""
def find_repeated_substrings(self, s, min_length=2):
"""Find repeated substrings"""
repeated = set()
for length in range(min_length, len(s) // 2 + 1):
hashes = self.rolling_hash(s, length)
hash_count = {}
for i, hash_val in enumerate(hashes):
substring = s[i:i + length]
if hash_val not in hash_count:
hash_count[hash_val] = []
hash_count[hash_val].append(substring)
for hash_val, substrings in hash_count.items():
if len(substrings) > 1:
repeated.add(substrings[0])
return list(repeated)
def are_equal(self, str1, str2):
"""Check if two strings are equal using rolling hash"""
if len(str1) != len(str2):
return False
return self.hash(str1) == self.hash(str2)
def find_palindromes(self, s):
"""Find palindromes using rolling hash"""
palindromes = []
for i in range(len(s)):
# Check odd length palindromes
left = right = i
while left >= 0 and right < len(s) and s[left] == s[right]:
if right - left + 1 > 1:
palindromes.append(s[left:right + 1])
left -= 1
right += 1
# Check even length palindromes
left, right = i, i + 1
while left >= 0 and right < len(s) and s[left] == s[right]:
palindromes.append(s[left:right + 1])
left -= 1
right += 1
return palindromes
def measure_performance(self, text, pattern):
"""Performance measurement"""
import time
start_time = time.time()
matches = self.find_pattern(text, pattern)
end_time = time.time()
return {
'matches': matches,
'count': len(matches),
'execution_time': end_time - start_time
}
# Utility functions
def create_rolling_hash(base=256, mod=1000000007):
return RollingHash(base, mod)
def find_pattern_with_rolling_hash(text, pattern, base=256, mod=1000000007):
rh = RollingHash(base, mod)
return rh.find_pattern(text, pattern)
def find_longest_common_substring_with_rolling_hash(str1, str2, base=256, mod=1000000007):
rh = RollingHash(base, mod)
return rh.find_longest_common_substring(str1, str2)
def find_repeated_substrings_with_rolling_hash(s, min_length=2, base=256, mod=1000000007):
rh = RollingHash(base, mod)
return rh.find_repeated_substrings(s, min_length)