Aho-Corasick algorithm
Let there be a set of strings with the total length $m$ (sum of all lengths). The Aho-Corasick algorithm constructs a data structure similar to […]
Month: July 2021
Suffix Array
1. Definition Let $s$ be a string of length $n$. The $i$-th suffix of $s$ is the substring $s[i \ldots n – 1]$. A suffix array will […]
Z-function and its calculation
1. Overview Suppose we are given a string $s$ of length $n$. The Z-function for this string is an array of length $n$ where the $i$-th element […]
Prefix function. Knuth–Morris–Pratt algorithm
1. Prefix function definition You are given a string $s$ of length $n$. The prefix function for this string is defined as an array $\pi$ of length […]
Rabin-Karp Algorithm for string matching
1. Overview This algorithm is based on the concept of hashing, so if you are not familiar with string hashing, refer to the string hashing article. This […]
String Hashing
Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing strings efficiently. The brute force way of […]
Finding the largest zero submatrix
You are given a matrix with n rows and m columns. Find the largest submatrix consisting of only zeros (a submatrix is a rectangular area of the matrix). 1. […]
Dynamic Programming on Broken Profile
Common problems solved using DP on broken profile include: finding number of ways to fully fill an area (e.g. chessboard/grid) with some figures (e.g. dominoes) […]
Divide and Conquer DP
Divide and Conquer is a dynamic programming optimization. 1. Preconditions Some dynamic programming problems have a recurrence of this form: $$dp(i, j) = \min_{0 \leq […]
Deleting from a data structure in $O(T(n)\log n)$
Suppose you have a data structure which allows adding elements in true $O(T(n))$. This article will describe a technique that allows deletion in $O(T(n)\log n)$ offline. 1. […]
Randomized Heap
A randomized heap is a heap that, through using randomization, allows to perform all operations in expected logarithmic time. A min heap is a binary tree in […]
Treap (Cartesian tree)
Treap is a data structure which combines binary tree and binary heap (hence the name: tree + heap $\Rightarrow$ Treap). More specifically, treap is a […]
Segment Tree
A Segment Tree is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the […]
Sqrt Decomposition
Sqrt Decomposition is a method (or a data structure) that allows you to perform some common operations (finding sum of the elements of the sub-array, […]
Fenwick Tree
Let, $f$ be some reversible function and $A$ be an array of integers of length $N$. Fenwick tree is a data structure which: calculates the value of […]
Disjoint Set Union
This article discusses the data structure Disjoint Set Union or DSU. Often it is also called Union Find because of its two main operations. This data structure provides the following […]
Sparse Table
Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its true power is […]
Minimum stack / Minimum queue
In this article we will consider three problems: first we will modify a stack in a way that allows us to find the smallest element […]
Operations on polynomials and series
In this article we will cover common operations that you will probably have to do if you deal with polynomials. 1. Basic Notion and Facts […]
