String Hashing

C++

1const ll M = 1e9 + 9, P = 9973; // Change M and P if you want to
2
3ll pw[100001]; // Stores the powers of P modulo M
4
5int n;
6string s;
7ll hsh[100001];
8
9void calc_hashes() {
10    hsh[0] = 1;

Java

1public static final long M = (long)1e9 + 9, P = 9973; // Change M and P if you want to
2
3public static long pw[] = new long[100001]; // Stores the powers of P modulo M
4
5public static int n;
6public static String s;
7public static long hsh[] = new long[100001];
8
9public static void calc_hashes() {
10    hsh[0] = 1;