AntInLoop

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)