Chapter 30 of 30
Hashing, String Algorithms & Geometry Basics
Master polynomial rolling hashing, tries, cross products, and the fundamental geometry concepts for competitive programming.
Polynomial Rolling HashingThe Trie (Prefix Tree)Geometry: The Cross ProductBook 1 Conclusion
Share:
Hashing, String Algorithms & Geometry Basics
The final chapter of Part 1 covers three powerful tools: hashing for substring comparison, tries for prefix-based problems, and the cross product for geometry basics.
Polynomial Rolling Hashing
Hash a string to a number so you can compare substrings in O(1):
Hash Function
code
hash(s) = (s[0] × p^0 + s[1] × p^1 + ... + s[n-1] × p^(n-1)) mod m
Where p is a base (typically 31 or 137) and m is a large prime (typically 10⁹ + 7 or 10⁹ + 9).
Implementation
hljs cpp
const int BASE = 31;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
struct Hash {
long long h1, h2;
Hash() : h1(0), h2(0) {}
Hash(long long a, long long b) : h1(a), h2(b) {}
bool operator==(const Hash &o) const { return h1 == o.h1 && h2 == o.h2; }
bool operator<(const Hash &o) const { return h1 != o.h1 ? h1 < o.h1 : h2 < o.h2; }
};
vector<Hash> computeHash(const string &s) {
int n = s.size();
vector<long long> pow1(n), pow2(n);
pow1[0] = pow2[0] = 1;
for (int i = 1; i < n; i++) {
pow1[i] = pow1[i - 1] * BASE % MOD1;
pow2[i] = pow2[i - 1] * BASE % MOD2;
}
vector<Hash> prefix(n + 1);
for (int i = 0; i < n; i++) {
prefix[i + 1].h1 = (prefix[i].h1 + (s[i] - 'a' + 1) * pow1[i]) % MOD1;
prefix[i + 1].h2 = (prefix[i].h2 + (s[i] - 'a' + 1) * pow2[i]) % MOD2;
}
return prefix;
}
// Hash of substring [l, r] (0-indexed)
Hash getHash(const vector<Hash> &prefix, int l, int r) {
long long h1 = (prefix[r + 1].h1 - prefix[l].h1 + MOD1 * MOD1) % MOD1;
long long h2 = (prefix[r + 1].h2 - prefix[l].h2 + MOD2 * MOD2) % MOD2;
h1 = h1 * /* inverse power */ ...; // normalize
return Hash(h1, h2);
}
Double Hashing
Using two moduli makes collisions extremely unlikely:
hljs cpp
Hash h1 = getHash(prefix1, l, r);
Hash h2 = getHash(prefix2, l, r);
// Compare both hashes for near-certain correctness
Applications
- Substring equality: O(1) after O(n) preprocessing
- Longest common substring: binary search + hashing
- Palindrome checking: forward hash vs reverse hash
The Trie (Prefix Tree)
A trie stores strings character by character, sharing common prefixes:
hljs cpp
struct Trie {
struct Node {
int children[26] = {};
int count = 0; // how many strings pass through this node
int endCount = 0; // how many strings end here
};
vector<Node> nodes = {Node()};
void insert(const string &s) {
int cur = 0;
for (char c : s) {
int idx = c - 'a';
if (!nodes[cur].children[idx]) {
nodes[cur].children[idx] = nodes.size();
nodes.push_back(Node());
}
cur = nodes[cur].children[idx];
nodes[cur].count++;
}
nodes[cur].endCount++;
}
bool search(const string &s) {
int cur = 0;
for (char c : s) {
int idx = c - 'a';
if (!nodes[cur].children[idx]) return false;
cur = nodes[cur].children[idx];
}
return nodes[cur].endCount > 0;
}
int countPrefix(const string &s) {
int cur = 0;
for (char c : s) {
int idx = c - 'a';
if (!nodes[cur].children[idx]) return 0;
cur = nodes[cur].children[idx];
}
return nodes[cur].count;
}
};
Trie Applications
- Prefix matching: count words with a given prefix
- Autocomplete: find all words with a given prefix
- XOR maximization: find the number that maximizes XOR with a given number
- String matching: find all strings in a set that match a pattern
XOR Maximization with Trie
hljs cpp
// Insert all numbers into a binary trie (bits from MSB to LSB)
// For each number, traverse the trie choosing the opposite bit when possible
int maxXOR(vector<int> &a) {
Trie trie;
for (int x : a) trie.insertBinary(x);
int result = 0;
for (int x : a) {
result = max(result, trie.maxXOR(x));
}
return result;
}
Geometry: The Cross Product
The cross product tells you the orientation of three points:
2D Cross Product
hljs cpp
long long cross(pair<long long,long long> a, pair<long long,long long> b, pair<long long,long long> c) {
return (b.first - a.first) * (c.second - a.second)
- (b.second - a.second) * (c.first - a.first);
}
Interpretation
cross > 0: counter-clockwise (left turn)cross < 0: clockwise (right turn)cross == 0: collinear
Applications
- Convex hull: sort by angle, maintain upper/lower hull
- Point in polygon: count winding number
- Line segment intersection: check orientations
Convex Hull (Graham Scan)
hljs cpp
vector<pair<long long,long long>> convexHull(vector<pair<long long,long long>> points) {
sort(points.begin(), points.end());
vector<pair<long long,long long>> hull;
// Lower hull
for (auto &p : points) {
while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], p) <= 0) {
hull.pop_back();
}
hull.push_back(p);
}
// Upper hull
int lowerSize = hull.size();
for (int i = points.size() - 2; i >= 0; i--) {
while ((int)hull.size() >= lowerSize + 1 && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
hull.pop_back(); // remove duplicate endpoint
return hull;
}
Book 1 Conclusion
Congratulations on completing Part 1 of Master Competitive Programming with C++! You've covered:
- C++ fundamentals: I/O, types, operators, fast I/O
- Core structures: arrays, strings, vectors, sets, maps
- Algorithms: sorting, binary search, two pointers, sliding window
- Math: number theory, modular arithmetic, combinatorics
- Data structures: stacks, queues, DSU, Fenwick/segment trees
- Graphs: DFS, BFS, Dijkstra, topological sort, trees
- DP: knapsack, LIS, bitmask DP
- Advanced: backtracking, hashing, tries, geometry basics
Part 2 will dive deeper into advanced algorithms: segment trees with lazy propagation, advanced DP, graph flows, and contest strategy.
Keep practicing on Codeforces, LeetCode, and AtCoder. The best way to learn is to solve problems.
Happy coding! 🚀
Prefer reading offline? Download the full book as a PDF.
Download Free Book