notebook.tex

\documentclass{article}

\usepackage{listings}
\usepackage{xcolor}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[default, semibold]{sourcecodepro}
\usepackage[default]{sourcesanspro}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[margin=0.6in, bmargin=0.6in, tmargin=0.2in, includehead]{geometry}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage{multicol}
\usepackage{graphicx}
\setlength{\multicolsep}{6.0pt plus 2.0pt minus 1.5pt}

\renewcommand\headrulewidth{0pt}

\usepackage{fancyhdr}
\fancypagestyle{plain}{
\fancyhead[R]{\bfseries\textcolor[HTML]{5c7c7e}{\thepage}}
\fancyhead[L]{\textcolor[HTML]{5c7c7e}{Lund University -- EZCP}}
\fancyfoot{}
}\pagestyle{plain}
\setlength{\headsep}{0.2in}
\setlength\parindent{0pt}
\setlength{\parskip}{0.25em}
\titleformat{\subsection}{\bfseries}{\thesection}{1.2em}{}
\titleformat{\section}{\normalfont\Large\bfseries}{\thesection}{1em}{}[{\titlerule[0.8pt]}]
\titlespacing{\section}{0pt}{0.5em}{0.5em}
\titlespacing{\subsection}{0pt}{0pt}{0.2em}

\lstset{
  backgroundcolor=\color{white},
  basicstyle=\ttfamily\footnotesize,
  breakatwhitespace=true,
  breaklines=true,
  keepspaces=true,
  numbers=left,
  numbersep=5pt,
  tabsize=4,
  rulecolor=\color{black},
  numberstyle=\tiny\color{black!50},
  stringstyle=\color[rgb]{0.58,0,0.82},
  commentstyle=\itshape\color{green!30!black},
  keywordstyle=\bfseries\color[HTML]{004d80},
  aboveskip=0.3 \baselineskip,
  belowskip=1.0 \baselineskip,
  postbreak=\mbox{\textcolor{red}{$\hookrightarrow$}\space}
}

\lstdefinelanguage{cpp}[]{C++}{
  morecomment=[is]{/**}{*/},
  morekeywords={ll, vector, pair, array, nullptr}
}

\begin{document}

\begin{titlepage}
  \centering
  \topskip0pt
  \vspace*{\fill}
  {\scshape\Huge EZCP \par}
  \vspace{1cm}
  {\LARGE\color{black!75} Lund University \par}
  \vspace*{\fill}
\end{titlepage}

\section*{Misc}

\subsection*{Template}
\lstinputlisting[language=cpp]{code/common.hpp}

\subsection*{Compilation Script}
\begin{lstlisting}[language=bash]
g++ --std=c++20 -Wall -Wshadow -Wno-conversion -Wfatal-errors -fsanitize=address,undefined -ftrapv -g $1 -o ${1%.cpp}.bin
\end{lstlisting}

\vspace*{-0.2cm}

\subsection*{Binary Search}
\lstinputlisting[language=cpp]{code/binary_search.cpp}

\vspace*{-0.2cm}

\subsection*{Ternary Search}
Find the smallest i in $[a,b]$ that maximizes $f(i)$, assuming that $f(a) < \dots < f(i) \ge \dots \ge f(b)$.

If there is a range of $f(i) \dots f(j)$ that are equal, change according to the comments to get the last index instead of the first.

\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/ternary_search.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/ternary_search.py}
\end{multicols}

\vspace*{-0.5cm}

\section*{Geometry}

\subsection*{Geometry Template (Python)}
\lstinputlisting[language=python]{code/geometry_py/geometry.py}

\subsection*{Geometry Template (C++)}
\lstinputlisting[language=cpp]{code/geometry_cpp/geometry.cpp}

\subsection*{Check if point is on a line segment}
\lstinputlisting[language=python]{code/geometry_py/on_segment.py}
\lstinputlisting[language=cpp]{code/geometry_cpp/on_segment.cpp}

\subsection*{Distance between point and line segment}
Returns the distance from the point p to the line segment starting at s and ending at e.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/dist_ps.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/dist_ps.py}
\end{multicols}

\vspace*{-0.5cm}

\subsection*{Distance between point and line}
Returns the signed distance from the point p to the line passing through the points a and b.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/dist_pl.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/dist_pl.py}
\end{multicols}

\subsection*{Intersection between two lines}
If a unique intersection point of the lines going through \lstinline{s1,e1} and \lstinline{s2,e2} exists \lstinline{(1,point)} is returned.\\
If no intersection point exists \lstinline{(0,(0,0))} is returned and if infinitely many exist \lstinline{(-1,(0,0))} is returned.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/intersect_ll.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/intersect_ll.py}
\end{multicols}

\subsection*{Intersection between two line segments}
If a unique intersection is found, returns a list with only this point.
If the segments intersect in many points, returns a list of 2 elements containing the
start and end of the common line segment. If no intersection, returns an empty list

\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/intersect_ss.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/intersect_ss.py}
\end{multicols}

\subsection*{Polygon area}
Returns twice the signed area of a polygon. Clockwise enumeration gives negative area.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/polygon_area.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/polygon_area.py}
\end{multicols}

\subsection*{Project point to line (or reflect)}
Projects the point p onto the line passing through a and b.
Set \lstinline{refl=True} to get reflection of point p across the line instead.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/proj_pl.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/proj_pl.py}
\end{multicols}

\subsection*{Point inside polygon}
Returns true if the point \lstinline{pt} lies within the polygon \lstinline{poly}.
If strict is true, returns false for points on the boundary.
\begin{multicols}{2}
\lstinputlisting[language=python]{code/geometry_py/point_in_polygon.py}
\columnbreak
\lstinputlisting[language=cpp]{code/geometry_cpp/point_in_polygon.cpp}
\end{multicols}

\vspace*{-1cm}

\subsection*{Circumcircle}
Returns a circle from three points.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/circumcircle.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/circumcircle.py}
\end{multicols}

\subsection*{Intersection between two circles}
Computes the pair of points at which two circles intersect. Returns \lstinline{None} in case of no intersection.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/intersect_cc.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/intersect_cc.py}
\end{multicols}

\subsection*{Intersection between circle and line}
Computes the intersection between a circle and a line. Returns a list of either 0, 1, or 2 intersection points.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/intersect_cl.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/intersect_cl.py}
\end{multicols}

\subsection*{Circle tangents}
Finds the external tangents of two circles, or internal if r2 is negated.\\
Can return 0, 1, or 2 tangents -- 0 if one circle contains the other (or overlaps it, in the internal case, or if the circles are the same);
1 if the circles are tangent to each other (in which case .first = .second and the tangent line is perpendicular to the line between the centers).
.first and .second give the tangency points at circle 1 and 2 respectively.
To find the tangents of a circle with a point set r2 to 0.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/circle_tangents.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/circle_tangents.py}
\end{multicols}

\subsection*{Circle-polygon area}
Returns the area of the intersection of a circle with a counter-clockwise polygon.
Time complexity: $\mathcal{O}(n)$
\lstinputlisting[language=cpp]{code/geometry_cpp/circle_poly_area.cpp}

\subsection*{Convex hull}
Returns a list of points on the convex hull in counter-clockwise order.
Points on the edge of the hull between two other points are not considered part of the hull.
Time complexity: $\mathcal{O}(n \log n)$
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/geometry_cpp/convex_hull.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/geometry_py/convex_hull.py}
\end{multicols}

\subsection*{Area of union of polygons}
Calculates the area of the union of multiple polygons (not necessarily convex).
The points within each polygon must be given in CCW order.
Time complexity: $\mathcal{O}(n^2)$, where $N$ is the total number of points.
\lstinputlisting[language=cpp]{code/geometry_cpp/polygon_union.cpp}

\subsection*{Angle struct}
Struct for representing angles using integer points and sorting them.
\lstinputlisting[language=cpp]{code/geometry_cpp/angle.cpp}

\subsection*{Half-plane intersection}
Computes the intersection of a set of half-planes, each on the form: $x P_x + y P_y \ge P_c$.

The resulting polygon extending to infinity is not handled. If that is possible add some extra half-planes far away and check for those in the result.

Each half-plane is given as a pair where the first value is $(P_x, P_y)$ and the second value is $P_c$.
In the returned vector, ret[i].first is the position of the i:th vertex and ret[i].second is the index in the input vector of the half-plane that created the edge between vertex i and (i+1)\%ret.size().

There may be duplicate points in the output vector if there are multiple half-planes that intersect at the same point.

\lstinputlisting[language=cpp]{code/geometry_cpp/half_plane_intersection.cpp}

\pagebreak

\section*{Data Structures}

\subsection*{Fenwick Tree}
\lstinputlisting[language=cpp, aboveskip=0pt]{code/fenwick_tree.cpp}

\subsection*{Segment Tree}
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/segtree.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/segtree.py}
\end{multicols}

\vspace*{-2.0cm}

\subsection*{Sparse Table}
\lstinputlisting[language=cpp, aboveskip=0pt]{code/sparse_table.cpp}

\pagebreak

\subsection*{Line Container}
Container where you can add lines of the form $kx + m$, and query maximum values at points $x$.
All operations are $\mathcal{O}(\log(n))$. For doubles, use \lstinline{inf = 1/.0} and \lstinline{div(a,b) = a/b}
\begin{multicols}{2}
\lstinputlisting[language=cpp]{code/line_container.cpp}
\end{multicols}

\subsection*{Lazy Segment Tree}
Segment tree with support for range updates. Use T = pair of value and index to get index from queries.\\
All ranges are \lstinline{(lo, hi]} (hi is not included).
\lstinline{fQuery} defines the function to be used for queries (currently min) and 
\lstinline{fUpdate} defines the function to be used for updates (currently addition).
\lstinputlisting[language=cpp]{code/lazy_segtree.cpp}

\subsection*{Heavy-Light Decomposition}
Constructs a heavy-light decomposition of a tree and generates indices for nodes that are consecutive within each heavy path.

For node \lstinline{i}, \lstinline{hchild[i]} is the heavy child (or $-1$ for leaf nodes),
\lstinline{hpLeaf[i]} and \lstinline{hpRoot[i]} are the leaf and root nodes of the heavy path passing through the node,
and \lstinline{arridx[i]} is the generated heavy path consecutive index (in the range $(0,n]$).
Within one heavy path, the deepest node has the lowest \lstinline{arridx[i]};

\lstinline{lca(a, b)} returns the lca of a and b.
If \lstinline{intv} is not null, \lstinline{*intv} will receive up to $2\log_2(n)$ non-overlapping intervals
such that there exists an interval \lstinline{i} $\in$ \lstinline{*intv} where \lstinline{i.first <= arridx[x] < i.second} iff. the node \lstinline{x} is on the path between a and b.\\
If \lstinline{intvIncludeLCA} is false, the lca of a and b will not be included in these intervals.
\lstinputlisting[language=cpp]{code/heavy_light_decomposition.cpp}

\pagebreak

\subsection*{Treap}
\begin{multicols}{2}
\lstinputlisting[language=cpp]{code/treap.cpp}
\end{multicols}

\subsection*{Link Cut Tree}
Represents a forest of unrooted trees. You can add and remove edges (as long as the result is still a forest), and check whether two nodes are in the same tree.
All operations are amortized $\mathcal{O}(\log(n))$.
\begin{multicols}{2}
\lstinputlisting[language=cpp]{code/link_cut_tree.cpp}
\end{multicols}


\section*{Graph Algorithms}
\subsection*{Maximum Flow (Dinic's Algorithm)}

Constructor takes number of nodes, call \lstinline{addEdge} to add edges and \lstinline{calc} to find maximum flow.
To obtain the actual flow, look at positive values of \lstinline{Edge::cap} only.

Time complexity: $\mathcal{O}(VE\log U)$ where $U = \max |\text{cap}|$.
$\mathcal{O}(\min(E^{1/2}, V^{2/3})E)$ if $U = 1$.
$\mathcal{O}(\sqrt{V}E)$ for bipartite matching.
\lstinputlisting[language=cpp]{code/max_flow.cpp}


\subsection*{Bellman Ford}

Calculates shortest paths from $s$ in a graph that might have negative edge weights.
Unreachable nodes get \lstinline{dist = inf}; nodes reachable through negative-weight cycles get \lstinline{dist = -inf}.
Assumes $V^2 \max |w_i| < 2^{63}$. Time complexity: $\mathcal{O}(VE)$
\begin{multicols}{2}
\lstinputlisting[language=cpp]{code/bellman_ford.cpp}
\end{multicols}


\subsection*{Floyd Warshall}
Calculates all-pairs shortest path in a directed graph.
As output, \lstinline{m[i][j]} is set to the shortest distance between $i$ and $j$,
\lstinline{inf} if no path, or \lstinline{-inf} if the path goes through a negative-weight cycle.
Time complexity: $\mathcal{O}(N^3)$.
\lstinputlisting[language=python]{code/floyd_warshall.py}
\lstinputlisting[language=cpp]{code/floyd_warshall.cpp}

\pagebreak

\subsection*{2-SAT}

Calculates a valid assignment to boolean variables in a 2-SAT problem.
Negated variables are represented by bit-inversions (\lstinline{~x}).
Time complexity: $\mathcal{O}(N+E)$, where $N$ is the number of boolean variables, and $E$ is the number of clauses.
\begin{multicols}{2}
\lstinputlisting[language=cpp]{code/2sat.cpp}
Usage:
\begin{lstlisting}[language=cpp]
TwoSat ts(number of boolean variables);
ts.either(0, ~3); // Var 0 is true or var 3 is false
ts.set_value(2); // Var 2 is true
ts.at_most_one({0,~1,2}); // <= 1 of vars 0, ~1 and 2 are true
ts.solve(); // Returns true iff it is solvable. ts.values holds the variables' values
\end{lstlisting}
\end{multicols}

\subsection*{Strongly Connected Components}

Finds strongly connected components in a directed graph.
Usage: \lstinline|scc(graph, [&](vector<int>& v) { ... })}| visits all components
in reverse topological order. \texttt{comp[i]} holds the component
index of a node (a component only has edges to components with
lower index). \texttt{ncomps} will contain the number of components.
Time complexity: $\mathcal{O}(E + V)$
\begin{multicols}{2}
\lstinputlisting[language=cpp]{code/scc.cpp}
\end{multicols}

\subsection*{Biconnected Components}

Finds all biconnected components in an undirected graph, and returns a list of edges in each. Time complexity: $\mathcal{O}(E + V)$.
Note that a node can be in several components, and bridges are by default returned as a single-edge biconnected component.

\lstinputlisting[language=cpp]{code/biconnected_components.cpp}

\subsection*{Weighted Bipartite Matching}

Given a weighted bipartite graph, matches every node on the left with a node on the right such that no nodes
are in two matchings and the sum of the edge weights is minimal.

Takes cost[N][M], where cost[i][j] = cost for L[i] to be matched with R[j] and returns (min cost, match), where L[i] is matched with R[match[i]]. Negate costs for max cost. Requires $N \le M$.
Time complexity: $\mathcal{O}(N^2 M)$

\lstinputlisting[language=cpp]{code/weighted_matching.cpp}

\subsection*{Minimum Cost Maximum Flow}

Calculates min-cost max-flow. \lstinline{cap[i][j]!=cap[j][i]} is allowed; double edges are not. To obtain the actual flow, look at positive values only. Time complexity: $\mathcal{O}(E^2)$.
If costs can be negative, call \lstinline{setpi} before \lstinline{maxflow}. Negative cost cycles are not supported.

\lstinputlisting[language=cpp]{code/min_cost_max_flow.cpp}

\vspace*{2cm}

\section*{Math}

\subsection*{Fast Modudo Operations}
\lstinputlisting[language=cpp]{code/modmul.cpp}

\subsection*{Is Prime (Miller-Rabin)}
Guaranteed to work for numbers up to $7 \cdot 10^{18}$. For larger numbers, use Python and extend A randomly.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/is_prime.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/is_prime.py}
\end{multicols}

\subsection*{Prime Factorization (Pollard-rho)}
Returns prime factors of a number, in arbitrary order.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/prime_factorize.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/prime_factorize.py}
\end{multicols}

\subsection*{Extended Euclidean Algorithm}
Finds the Greatest Common Divisor to the integers $a$ and $b$. Also finds two integers $x$ and $y$, such that $ax+by=\gcd(a,b)$.
Returns a tuple of $(\gcd(a, b), x, y)$. If $a$ and $b$ are coprime, then $x$ is the inverse of $a \pmod{b}$.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/euclid.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/euclid.py}
\end{multicols}

\subsection*{Chinese Remainder Theorem}
Finds the smallest number $x$ satisfying a system of congruences, each in the form $x \equiv r_i \pmod{m_i}$.
All pairs of $m_i$ must be coprime. \lstinline{eq} is a list of tuples describing the equations, the $i$:th of which should be $(r_i, m_i)$.
\begin{multicols}{2}
  \lstinputlisting[language=cpp]{code/crt.cpp}
  \columnbreak
  \lstinputlisting[language=python]{code/crt.py}
\end{multicols}

\subsection*{Solve Linear System of Equations}
Solves $A x = b$. If there are multiple solutions, an arbitrary one is returned.
Returns rank, or $-1$ if no solutions. Time complexity: $\mathcal{O}(n^2 m)$
\begin{multicols}{2}
\lstinputlisting[language=cpp]{code/solve_linear.cpp}
\end{multicols}

\subsection*{Matrix Multiplication}
\lstinputlisting[language=python]{code/matrix_mul.py}

\pagebreak

\subsection*{Spherical Distance}
\begin{multicols}{2}\lstinputlisting[language=cpp]{code/spherical_distance.cpp}
  \columnbreak
  Returns the shortest distance on the sphere with radius radius between the points
 with azimuthal angles (longitude) f1 ($\phi_1$) and f2 ($\phi_2$) from x axis and zenith angles
 (latitude) t1 ($\theta_1$) and t2 ($\theta_2$) from z axis (0 = north pole). All angles measured
 in radians. The algorithm starts by converting the spherical coordinates to cartesian coordinates
 so if that is what you have you can use only the two last rows. dx*radius is then the difference
 between the two points in the x direction and d*radius is the total distance between the points.
\end{multicols}

\subsection*{FFT}
\lstinline{fft(a)} computes $\hat f(k) = \sum_x a[x] \exp(2\pi i \cdot k x / N)$ for all $k$.
Useful for convolution: \lstinline{conv(a, b)=c}, where $c[x] = \sum a[i]b[x-i]$.

Rounding is safe if $(\sum a_i^2 + \sum b_i^2)\log_2{N} < 9\cdot10^{14}$
(in practice $10^{16}$; higher for random inputs).

Time complexity: $\mathcal{O}(N \log N)$ with $N = |A|+|B|$ (about $1s$ for $N=4 \cdot 10^6$)
\lstinputlisting[language=cpp]{code/fft.cpp}

\newpage

\subsection*{ModFFT}
\lstinline{fft(a)} computes $\hat f(k) = \sum_x a[x] g^{xk}$ for all $k$, where $g=\text{root}^{(M-1)/N}$. N must be a power of 2.

For conv, M should be of the form $2^a b+1$, and the convolution result should have size at most $2^a$. Inputs must be in $[0,M)$.

\lstinputlisting[language=cpp]{code/fft_mod.cpp}

\vspace*{-0.3cm}

\subsection*{Fraction Binary Search}
Given $f$ and $N$, finds the smallest fraction $p/q \in [0, 1]$ such that $f(p/q)$ is true, and $p, q \le N$.
\lstinputlisting[language=cpp]{code/fraction_binary_search.cpp}

\subsection*{Fraction}
\lstinputlisting[language=cpp]{code/fraction.cpp}

\begin{multicols}{2}
\subsection*{Polynomial Roots}
Finds the real roots of a polynomial. Time complexity: $\mathcal{O}(n^2 \log(1/\epsilon))$.
Usage (solves $x^2-3x+2 = 0$): \lstinline[language=cpp]|poly_roots({{ 2, -3, 1 }},-1e9,1e9)|
\lstinputlisting[language=cpp]{code/poly_roots.cpp}
\columnbreak
\subsection*{Matrix Inverse}
Invert matrix $A$. Returns rank; result is stored in $A$ unless singular (rank < n). Time complexity: $\mathcal{O}(n^3)$
\lstinputlisting[language=cpp]{code/matrix_invert.cpp}
\end{multicols}

\newpage

\subsection*{Simplex}
Solves a general linear maximization problem: maximize $c^T x$ subject to $Ax \le b$, $x \ge 0$.

Returns -inf if there is no solution, inf if there are arbitrarily good solutions, or the maximum value of $c^T x$ otherwise.

The input vector is set to an optimal $x$ (or in the unbounded case, an arbitrary solution fulfilling the constraints).

Numerical stability is not guaranteed. For better performance, define variables such that $x = 0$ is viable.

 \text{vvd A = \{\{1,-1\}, \{-1,1\}, \{-1,-2\}\};}
 \text{vd b = \{1,1,-4\}, c = \{-1,-1\}, x;}
 T val = LPSolver(A, b, c).solve(x);
 
 $O(NM * \#pivots)$, where a pivot may be e.g. an edge relaxation. $O(2^n)$ in the general case.

\lstinputlisting[language=cpp]{code/simplex.cpp}



\vspace*{1cm}

\section*{Strings}


\begin{multicols}{2}

\subsection*{Manacher}
  For each position in a string, computes p[0][i] = half length of
longest even palindrome around pos i, p[1][i] = longest odd (half rounded down).
Time: O(N)
  \lstinputlisting[language=cpp]{code/manacher.cpp}
  \columnbreak


  \subsection*{Polynomial Hash}
  \lstinputlisting[language=cpp]{code/poly_hash.cpp}
\end{multicols}

\subsection*{Aho Corasick}
Aho-Corasick automaton, used for multiple pattern matching.
\\Initialize with AhoCorasick ac(patterns); the automaton start node will be at index 0.
\\find(word) returns for each position the index of the longest word that ends there, or -1 if none.
\\findAll($-$, word) finds all words (up to $N \sqrt N$ many if no duplicate patterns)
\\that start at each position (shortest first).
\\Duplicate patterns are allowed; empty patterns are not.
\\To find the longest words that start at each position, reverse all input.
\\For large alphabets, split each symbol into chunks, with sentinel bits for symbol boundaries.
\\Time: construction takes $O(26N)$, where $N =$ sum of length of patterns.
\\find(x) is $O(N)$, where N = length of x. findAll is $O(NM)$.
  \lstinputlisting[language=cpp]{code/aho_corasick.cpp}

  \subsection*{Suffix tree}
  Ukkonen's algorithm for online suffix tree construction.
\\Each node contains indices [l, r) into the string, and a list of child nodes.
\\Suffixes are given by traversals of this tree, joining [l, r) substrings.
\\The root is 0 (has l = -1, r = 0), non-existent children are -1.
\\To get a complete tree, append a dummy symbol -- otherwise it may contain
\\an incomplete path (still useful for substring matching, though).
    \lstinputlisting[language=cpp]{code/suffix_tree.cpp}


\subsection*{Estimates}

\begin{multicols}{2}
	$\sum_{d|n} d = O(n \log \log n).$
	
	The number of divisors of $n$ is at most around 100 for $n < 5e4$, 500 for $n < 1e7$, 2000 for $n < 1e10$, 200\,000 for $n < 1e19$.
	
	\columnbreak
	
	Number of ways of writing $n$ as a sum of positive integers, disregarding the order of the summands.
	$$ p(0) = 1,  p(n) = \sum_{k \in \mathbb{Z} \setminus \{0\}} (-1)^{k+1} p(n - k(3k-1) / 2) $$
	\[ p(n) \sim 0.145 / n \cdot \exp(2.56 \sqrt{n}) \]
	
	\begin{center}
		\begin{tabular}{c|c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c}
			$n$    & 0 & 1 & 2 & 3 & 4 & 5 & 6  & 7  & 8  & 9  & 20  & 50  & 100 \\ \hline
			$p(n)$ & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 627 & $\mathtt{\sim}$2e5 & $\mathtt{\sim}$2e8 \\
		\end{tabular}
	\end{center}
	
\end{multicols}



\end{document}