René's URL Explorer Experiment


Title: String Hashing - Algorithms for Competitive Programming

Description: The goal of this project is to translate the wonderful resource http://e-maxx.ru/algo which provides descriptions of many algorithms and data structures especially popular in field of competitive programming. Moreover we want to improve the collected knowledge by extending the articles and adding new articles to the collection.

Generator: mkdocs-1.6.1, mkdocs-material-9.7.1

direct link

Domain: cp-algorithms.com

Links:

Skip to content https://cp-algorithms.com/string/string-hashing.html#string-hashing
https://cp-algorithms.com/
Algorithms for Competitive Programming https://cp-algorithms.com/
String Hashing https://cp-algorithms.com/string/string-hashing.html
cp-algorithms/cp-algorithms https://github.com/cp-algorithms/cp-algorithms
https://cp-algorithms.com/feed_rss_created.xml
https://discord.gg/HZ5AecN3KX
https://github.com/sponsors/cp-algorithms
https://cp-algorithms.com/
cp-algorithms/cp-algorithms https://github.com/cp-algorithms/cp-algorithms
Main Page https://cp-algorithms.com/index.html
Navigation https://cp-algorithms.com/navigation.html
Tag index https://cp-algorithms.com/tags.html
How to Contribute https://cp-algorithms.com/contrib.html
Code of conduct https://cp-algorithms.com/code_of_conduct.html
Preview https://cp-algorithms.com/preview.html
Binary Exponentiation https://cp-algorithms.com/algebra/binary-exp.html
Euclidean algorithm for computing the greatest common divisor https://cp-algorithms.com/algebra/euclid-algorithm.html
Extended Euclidean Algorithm https://cp-algorithms.com/algebra/extended-euclid-algorithm.html
Linear Diophantine Equations https://cp-algorithms.com/algebra/linear-diophantine-equation.html
Fibonacci Numbers https://cp-algorithms.com/algebra/fibonacci-numbers.html
Sieve of Eratosthenes https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
Linear Sieve https://cp-algorithms.com/algebra/prime-sieve-linear.html
Primality tests https://cp-algorithms.com/algebra/primality_tests.html
Integer factorization https://cp-algorithms.com/algebra/factorization.html
Euler's totient function https://cp-algorithms.com/algebra/phi-function.html
Number of divisors / sum of divisors https://cp-algorithms.com/algebra/divisors.html
Modular Inverse https://cp-algorithms.com/algebra/module-inverse.html
Linear Congruence Equation https://cp-algorithms.com/algebra/linear_congruence_equation.html
Chinese Remainder Theorem https://cp-algorithms.com/algebra/chinese-remainder-theorem.html
Garner's Algorithm https://cp-algorithms.com/algebra/garners-algorithm.html
Factorial modulo p https://cp-algorithms.com/algebra/factorial-modulo.html
Discrete Log https://cp-algorithms.com/algebra/discrete-log.html
Primitive Root https://cp-algorithms.com/algebra/primitive-root.html
Discrete Root https://cp-algorithms.com/algebra/discrete-root.html
Montgomery Multiplication https://cp-algorithms.com/algebra/montgomery_multiplication.html
Balanced Ternary https://cp-algorithms.com/algebra/balanced-ternary.html
Gray code https://cp-algorithms.com/algebra/gray-code.html
Bit manipulation https://cp-algorithms.com/algebra/bit-manipulation.html
Enumerating submasks of a bitmask https://cp-algorithms.com/algebra/all-submasks.html
Arbitrary-Precision Arithmetic https://cp-algorithms.com/algebra/big-integer.html
Fast Fourier transform https://cp-algorithms.com/algebra/fft.html
Operations on polynomials and series https://cp-algorithms.com/algebra/polynomial.html
Continued fractions https://cp-algorithms.com/algebra/continued-fractions.html
Factoring Exponentiation https://cp-algorithms.com/algebra/factoring-exp.html
Minimum Stack / Minimum Queue https://cp-algorithms.com/data_structures/stack_queue_modification.html
Sparse Table https://cp-algorithms.com/data_structures/sparse-table.html
Disjoint Set Union https://cp-algorithms.com/data_structures/disjoint_set_union.html
Fenwick Tree https://cp-algorithms.com/data_structures/fenwick.html
Sqrt Decomposition https://cp-algorithms.com/data_structures/sqrt_decomposition.html
Segment Tree https://cp-algorithms.com/data_structures/segment_tree.html
Treap https://cp-algorithms.com/data_structures/treap.html
Sqrt Tree https://cp-algorithms.com/data_structures/sqrt-tree.html
Randomized Heap https://cp-algorithms.com/data_structures/randomized_heap.html
Deleting from a data structure in O(T(n) log n) https://cp-algorithms.com/data_structures/deleting_in_log_n.html
Introduction to Dynamic Programming https://cp-algorithms.com/dynamic_programming/intro-to-dp.html
Knapsack Problem https://cp-algorithms.com/dynamic_programming/knapsack.html
Longest increasing subsequence https://cp-algorithms.com/dynamic_programming/longest_increasing_subsequence.html
Divide and Conquer DP https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html
Knuth's Optimization https://cp-algorithms.com/dynamic_programming/knuth-optimization.html
Dynamic Programming on Broken Profile. Problem "Parquet" https://cp-algorithms.com/dynamic_programming/profile-dynamics.html
Finding the largest zero submatrix https://cp-algorithms.com/dynamic_programming/zero_matrix.html
String Hashing https://cp-algorithms.com/string/string-hashing.html
Calculation of the hash of a string https://cp-algorithms.com/string/string-hashing.html#calculation-of-the-hash-of-a-string
Example tasks https://cp-algorithms.com/string/string-hashing.html#example-tasks
Search for duplicate strings in an array of strings https://cp-algorithms.com/string/string-hashing.html#search-for-duplicate-strings-in-an-array-of-strings
Fast hash calculation of substrings of given string https://cp-algorithms.com/string/string-hashing.html#fast-hash-calculation-of-substrings-of-given-string
Applications of Hashing https://cp-algorithms.com/string/string-hashing.html#applications-of-hashing
Determine the number of different substrings in a string https://cp-algorithms.com/string/string-hashing.html#determine-the-number-of-different-substrings-in-a-string
Improve no-collision probability https://cp-algorithms.com/string/string-hashing.html#improve-no-collision-probability
Practice Problems https://cp-algorithms.com/string/string-hashing.html#practice-problems
Rabin-Karp for String Matching https://cp-algorithms.com/string/rabin-karp.html
Prefix function - Knuth-Morris-Pratt https://cp-algorithms.com/string/prefix-function.html
Z-function https://cp-algorithms.com/string/z-function.html
Suffix Array https://cp-algorithms.com/string/suffix-array.html
Aho-Corasick algorithm https://cp-algorithms.com/string/aho_corasick.html
Suffix Tree https://cp-algorithms.com/string/suffix-tree-ukkonen.html
Suffix Automaton https://cp-algorithms.com/string/suffix-automaton.html
Lyndon factorization https://cp-algorithms.com/string/lyndon_factorization.html
Expression parsing https://cp-algorithms.com/string/expression_parsing.html
Manacher's Algorithm - Finding all sub-palindromes in O(N) https://cp-algorithms.com/string/manacher.html
Finding repetitions https://cp-algorithms.com/string/main_lorentz.html
Gauss & System of Linear Equations https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
Gauss & Determinant https://cp-algorithms.com/linear_algebra/determinant-gauss.html
Kraut & Determinant https://cp-algorithms.com/linear_algebra/determinant-kraut.html
Rank of a matrix https://cp-algorithms.com/linear_algebra/rank-matrix.html
Finding Power of Factorial Divisor https://cp-algorithms.com/algebra/factorial-divisors.html
Binomial Coefficients https://cp-algorithms.com/combinatorics/binomial-coefficients.html
Catalan Numbers https://cp-algorithms.com/combinatorics/catalan-numbers.html
The Inclusion-Exclusion Principle https://cp-algorithms.com/combinatorics/inclusion-exclusion.html
Burnside's lemma / Pólya enumeration theorem https://cp-algorithms.com/combinatorics/burnside.html
Stars and bars https://cp-algorithms.com/combinatorics/stars_and_bars.html
Generating all K-combinations https://cp-algorithms.com/combinatorics/generating_combinations.html
Placing Bishops on a Chessboard https://cp-algorithms.com/combinatorics/bishops-on-chessboard.html
Balanced bracket sequences https://cp-algorithms.com/combinatorics/bracket_sequences.html
Counting labeled graphs https://cp-algorithms.com/combinatorics/counting_labeled_graphs.html
Binary Search https://cp-algorithms.com/num_methods/binary_search.html
Ternary Search https://cp-algorithms.com/num_methods/ternary_search.html
Newton's method for finding roots https://cp-algorithms.com/num_methods/roots_newton.html
Simulated Annealing https://cp-algorithms.com/num_methods/simulated_annealing.html
Integration by Simpson's formula https://cp-algorithms.com/num_methods/simpson-integration.html
Basic Geometry https://cp-algorithms.com/geometry/basic-geometry.html
Finding the equation of a line for a segment https://cp-algorithms.com/geometry/segment-to-line.html
Intersection Point of Lines https://cp-algorithms.com/geometry/lines-intersection.html
Check if two segments intersect https://cp-algorithms.com/geometry/check-segments-intersection.html
Intersection of Segments https://cp-algorithms.com/geometry/segments-intersection.html
Circle-Line Intersection https://cp-algorithms.com/geometry/circle-line-intersection.html
Circle-Circle Intersection https://cp-algorithms.com/geometry/circle-circle-intersection.html
Common tangents to two circles https://cp-algorithms.com/geometry/tangents-to-two-circles.html
Length of the union of segments https://cp-algorithms.com/geometry/length-of-segments-union.html
Oriented area of a triangle https://cp-algorithms.com/geometry/oriented-triangle-area.html
Area of simple polygon https://cp-algorithms.com/geometry/area-of-simple-polygon.html
Check if points belong to the convex polygon in O(log N) https://cp-algorithms.com/geometry/point-in-convex-polygon.html
Minkowski sum of convex polygons https://cp-algorithms.com/geometry/minkowski.html
Pick's Theorem - area of lattice polygons https://cp-algorithms.com/geometry/picks-theorem.html
Lattice points of non-lattice polygon https://cp-algorithms.com/geometry/lattice-points.html
Convex hull construction https://cp-algorithms.com/geometry/convex-hull.html
Convex hull trick and Li Chao tree https://cp-algorithms.com/geometry/convex_hull_trick.html
Search for a pair of intersecting segments https://cp-algorithms.com/geometry/intersecting_segments.html
Finding faces of a planar graph https://cp-algorithms.com/geometry/planar.html
Point location in O(log N) https://cp-algorithms.com/geometry/point-location.html
Finding the nearest pair of points https://cp-algorithms.com/geometry/nearest_points.html
Delaunay triangulation and Voronoi diagram https://cp-algorithms.com/geometry/delaunay.html
Vertical decomposition https://cp-algorithms.com/geometry/vertical_decomposition.html
Half-plane intersection - S&I Algorithm in O(N log N) https://cp-algorithms.com/geometry/halfplane-intersection.html
Manhattan Distance https://cp-algorithms.com/geometry/manhattan-distance.html
Minimum Enclosing Circle https://cp-algorithms.com/geometry/enclosing-circle.html
Breadth First Search https://cp-algorithms.com/graph/breadth-first-search.html
Depth First Search https://cp-algorithms.com/graph/depth-first-search.html
Finding Connected Components https://cp-algorithms.com/graph/search-for-connected-components.html
Finding Bridges in O(N+M) https://cp-algorithms.com/graph/bridge-searching.html
Finding Bridges Online https://cp-algorithms.com/graph/bridge-searching-online.html
Finding Articulation Points in O(N+M) https://cp-algorithms.com/graph/cutpoints.html
Strongly Connected Components and Condensation Graph https://cp-algorithms.com/graph/strongly-connected-components.html
Strong Orientation https://cp-algorithms.com/graph/strong-orientation.html
Dijkstra - finding shortest paths from given vertex https://cp-algorithms.com/graph/dijkstra.html
Dijkstra on sparse graphs https://cp-algorithms.com/graph/dijkstra_sparse.html
Bellman-Ford - finding shortest paths with negative weights https://cp-algorithms.com/graph/bellman_ford.html
0-1 BFS https://cp-algorithms.com/graph/01_bfs.html
D´Esopo-Pape algorithm https://cp-algorithms.com/graph/desopo_pape.html
Floyd-Warshall - finding all shortest paths https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html
Number of paths of fixed length / Shortest paths of fixed length https://cp-algorithms.com/graph/fixed_length_paths.html
Minimum Spanning Tree - Prim's Algorithm https://cp-algorithms.com/graph/mst_prim.html
Minimum Spanning Tree - Kruskal https://cp-algorithms.com/graph/mst_kruskal.html
Minimum Spanning Tree - Kruskal with Disjoint Set Union https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html
Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor https://cp-algorithms.com/graph/second_best_mst.html
Kirchhoff Theorem https://cp-algorithms.com/graph/kirchhoff-theorem.html
Prüfer code https://cp-algorithms.com/graph/pruefer_code.html
Checking a graph for acyclicity and finding a cycle in O(M) https://cp-algorithms.com/graph/finding-cycle.html
Finding a Negative Cycle in the Graph https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html
Eulerian Path https://cp-algorithms.com/graph/euler_path.html
Lowest Common Ancestor https://cp-algorithms.com/graph/lca.html
Lowest Common Ancestor - Binary Lifting https://cp-algorithms.com/graph/lca_binary_lifting.html
Lowest Common Ancestor - Farach-Colton and Bender algorithm https://cp-algorithms.com/graph/lca_farachcoltonbender.html
Solve RMQ by finding LCA https://cp-algorithms.com/graph/rmq_linear.html
Lowest Common Ancestor - Tarjan's off-line algorithm https://cp-algorithms.com/graph/lca_tarjan.html
Maximum flow - Ford-Fulkerson and Edmonds-Karp https://cp-algorithms.com/graph/edmonds_karp.html
Maximum flow - Push-relabel algorithm https://cp-algorithms.com/graph/push-relabel.html
Maximum flow - Push-relabel algorithm improved https://cp-algorithms.com/graph/push-relabel-faster.html
Maximum flow - Dinic's algorithm https://cp-algorithms.com/graph/dinic.html
Maximum flow - MPM algorithm https://cp-algorithms.com/graph/mpm.html
Flows with demands https://cp-algorithms.com/graph/flow_with_demands.html
Minimum-cost flow https://cp-algorithms.com/graph/min_cost_flow.html
Assignment problem https://cp-algorithms.com/graph/Assignment-problem-min-flow.html
Bipartite Graph Check https://cp-algorithms.com/graph/bipartite-check.html
Kuhn's Algorithm - Maximum Bipartite Matching https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html
Hungarian Algorithm https://cp-algorithms.com/graph/hungarian-algorithm.html
Topological Sorting https://cp-algorithms.com/graph/topological-sort.html
Edge connectivity / Vertex connectivity https://cp-algorithms.com/graph/edge_vertex_connectivity.html
Tree painting https://cp-algorithms.com/graph/tree_painting.html
2-SAT https://cp-algorithms.com/graph/2SAT.html
Heavy-light decomposition https://cp-algorithms.com/graph/hld.html
RMQ task (Range Minimum Query - the smallest element in an interval) https://cp-algorithms.com/sequences/rmq.html
Search the subsegment with the maximum/minimum sum https://cp-algorithms.com/others/maximum_average_segment.html
K-th order statistic in O(N) https://cp-algorithms.com/sequences/k-th.html
MEX task (Minimal Excluded element in an array) https://cp-algorithms.com/sequences/mex.html
Games on arbitrary graphs https://cp-algorithms.com/game_theory/games_on_graphs.html
Sprague-Grundy theorem. Nim https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
Scheduling jobs on one machine https://cp-algorithms.com/schedules/schedule_one_machine.html
Scheduling jobs on two machines https://cp-algorithms.com/schedules/schedule_two_machines.html
Optimal schedule of jobs given their deadlines and durations https://cp-algorithms.com/schedules/schedule-with-completion-duration.html
Tortoise and Hare Algorithm (Linked List cycle detection) https://cp-algorithms.com/others/tortoise_and_hare.html
Josephus problem https://cp-algorithms.com/others/josephus_problem.html
15 Puzzle Game: Existence Of The Solution https://cp-algorithms.com/others/15-puzzle.html
The Stern-Brocot Tree and Farey Sequences https://cp-algorithms.com/others/stern_brocot_tree_farey_sequences.html
https://github.com/cp-algorithms/cp-algorithms/edit/main/src/string/string-hashing.md
https://cp-algorithms.com/string/string-hashing.html
https://github.com/cp-algorithms/cp-algorithms/commits/main/src/string/string-hashing.md
Translated https://cp-algorithms.com/tags.html#tag:translated
From: e-maxx.ru https://e-maxx.ru/algo/string_hashes
https://cp-algorithms.com/string/string-hashing.html#string-hashing
https://cp-algorithms.com/string/string-hashing.html#calculation-of-the-hash-of-a-string
https://cp-algorithms.com/string/string-hashing.html#example-tasks
https://cp-algorithms.com/string/string-hashing.html#search-for-duplicate-strings-in-an-array-of-strings
https://cp-algorithms.com/string/string-hashing.html#fast-hash-calculation-of-substrings-of-given-string
modular multiplicative inversehttps://cp-algorithms.com/algebra/module-inverse.html
https://cp-algorithms.com/string/string-hashing.html#applications-of-hashing
Rabin-Karp algorithmhttps://cp-algorithms.com/string/rabin-karp.html
https://cp-algorithms.com/string/string-hashing.html#determine-the-number-of-different-substrings-in-a-string
Suffix Arrayshttps://cp-algorithms.com/string/suffix-array.html
Suffix Treehttps://cp-algorithms.com/string/suffix-tree-ukkonen.html
Suffix Automatonhttps://cp-algorithms.com/string/suffix-automaton.html
https://cp-algorithms.com/string/string-hashing.html#improve-no-collision-probability
https://cp-algorithms.com/string/string-hashing.html#practice-problems
Good Substrings - Codeforceshttps://codeforces.com/contest/271/problem/D
A Needle in the Haystack - SPOJhttp://www.spoj.com/problems/NHAY/
String Hashing - Kattishttps://open.kattis.com/problems/hashing
Double Profiles - Codeforceshttp://codeforces.com/problemset/problem/154/C
Password - Codeforceshttp://codeforces.com/problemset/problem/126/B
SUB_PROB - SPOJhttp://www.spoj.com/problems/SUB_PROB/
INSQ15_Ahttps://www.codechef.com/problems/INSQ15_A
SPOJ - Ada and Spring Cleaninghttp://www.spoj.com/problems/ADACLEAN/
GYM - Text Editorhttp://codeforces.com/gym/101466/problem/E
12012 - Detection of Extraterrestrialhttps://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3163
Codeforces - Games on a CDhttp://codeforces.com/contest/727/problem/E
UVA 11855 - Buzzwordshttps://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2955
Codeforces - Santa Claus and a Palindromehttp://codeforces.com/contest/752/problem/D
Codeforces - String Compressionhttp://codeforces.com/contest/825/problem/F
Codeforces - Palindromic Characteristicshttp://codeforces.com/contest/835/problem/D
SPOJ - Testhttp://www.spoj.com/problems/CF25E/
Codeforces - Palindrome Degreehttp://codeforces.com/contest/7/problem/D
Codeforces - Deletion of Repeatshttp://codeforces.com/contest/19/problem/C
HackerRank - Gift Boxeshttps://www.hackerrank.com/contests/womens-codesprint-5/challenges/gift-boxes
jakobkoglerhttps://github.com/jakobkogler
paramsinghhttps://github.com/paramsingh
gaurav-singh1998https://github.com/gaurav-singh1998
Morasshttps://github.com/Morass
adamant-pwnhttps://github.com/adamant-pwn
tcNickolashttps://github.com/tcNickolas
likecshttps://github.com/likecs
mhayterhttps://github.com/mhayter
minhazmirazhttps://github.com/minhazmiraz
MayankPrataphttps://github.com/MayankPratap
vedant-zhttps://github.com/vedant-z
Taglhttps://github.com/Tagl
hanzala-sohrabhttps://github.com/hanzala-sohrab
Tahanimahttps://github.com/Tahanima
Siddharths8212376https://github.com/Siddharths8212376
Creative Commons Attribution Share Alike 4.0 Internationalhttps://github.com/cp-algorithms/cp-algorithms/blob/main/LICENSE
cp-algorithms contributorshttps://github.com/cp-algorithms/cp-algorithms/graphs/contributors
Material for MkDocs https://squidfunk.github.io/mkdocs-material/
https://github.com/cp-algorithms/cp-algorithms
https://discord.gg/HZ5AecN3KX
https://github.com/sponsors/cp-algorithms

Viewport: width=device-width,initial-scale=1

URLs of crawlers that visited me.