This blog is for compiling my learning and way of insight into solving a problem, some might benefit from this so enjoy

Theory:

• Hashing is a way to convert string/number to a number using base converting ex: 10 into base2 = 110
• so you convert string by converting each character a,b,c...z into 0,1,2,3...,26 into a base
• but the base must be modded to ensure the number dont explode but this create a collision probability -> two number can be the same (mod MOD)

Template: const ll Mod = 1000000009LL; const ll Base = 271LL;

struct hashed_string{ private: string s; ll n; vector prefix; vector pow; public: hashed_string(string a){ s = a; n = a.size(); prefix.assign(n, 0); ll sum = 0; pow.assign(n+1, 0); pow[0] = 1; for (int i = 1; i <= n; i++){ pow[i] = (pow[i-1] * Base) % Mod; } for (int i = 0; i < n; i++){ prefix[i] = ((sum * Base) % Mod + s[i] — 'a' + 1) % Mod; sum = prefix[i]; } } ll get_hash(ll l, ll r){ ll x = prefix[r]; if (l >= 1){ l--; x = ((x — prefix[l] * pow[r — l] % Mod) % Mod + Mod) % Mod; } return x; } };

Problemlist:

Problem 1: https://cses.fi/problemset/task/1733 + THis problem is template hashing -> complexity is N/1 + N/2 + N/3,.... (N ln N estimated). + for every compare each segment, [j, j + i — 1] does it equal to the segment [0, i — 1] and compare the suffix if it is equal to the part of the prefix

Problem 2: https://usaco.org/index.php?page=viewproblem2&cpid=529〈=en +