Skip to content

Instantly share code, notes, and snippets.

@andriybuday

andriybuday/RollingHash.java

Created February 24, 2020 03:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save andriybuday/d2009edaa98f993770f49a45d24fc520 to your computer and use it in GitHub Desktop.
Save andriybuday/d2009edaa98f993770f49a45d24fc520 to your computer and use it in GitHub Desktop.
Download ZIP
RollingHash
Raw
RollingHash.java
int mod = 1000000007;
int p = 97; //prime
long hash = 0, power = 1;
for(char c: str) {
long add = ((long)c * power);
hash += add;
hash %= mod;
power = power * p % mod;
}
// in mod space x/p is the same as x*pinv
int pinv = BigInteger.valueOf(p).modInverse(BigInteger.valueOf(mod)).intValue();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment