acm-algorithm-template

Some algorithm templates for competitive programming. Trying to be extensive and easy to use.

There are two branches: master and icpc. The master branch is for online contest and on-site contests that don't limit the number of pages of your reference so this branch will try to be as extensive as possible. On the other hand, the icpc branch is for some ICPC contest that limit the number of pages of your reference so you can't just print everything and the coding style may also change in order to save space.

There are (maybe incomplete, I'm too lazy to update):

String:

• Trie
• KMP
• Z-function
• Aho-Corasick(AC) automaton
• Manacher
• Suffix array
• Suffix automaton
• Sting hashing

Data stucture

• Segment tree
• Fenwick tree
• Persistent segtree
• Sparse table
• Treap
• Union Find

Graph theory

• Augmented path algorithm for bipartite matching
• Bellman Ford for finding negative cycle
• Binary Lifting and Lowest Common Ancestor
• Bridges Finding
• Cut Vertices Finding
• Dijkstra
• Dinic algorithm for max flow
• Divide and Conquer on Trees (aka Centroid Decomposition)
• Euler Tour
• Heavy-light decomposition
• Hopcroft-Karp algorithm for bipartite matching
• Hungarian
• Push-relabel algorithm for max flow
• Strongly connected components (Tarjan and Kosaraju)
• Two-edge connected components (Tarjan)

Math:

• BSGS
• Chinese Remainder Theorem
• Extended Euclidean algorithm
• Euler's totient function
• Factorization
• FFT
• Gauss-Jordan elimination
• Linear sieve
• Modular Multiplicative Inverse
• Mod int
• DFT
• Simplex

Geometry:

• Angle
• Circle
• General stuff
• Line
• Point
• Polygon
• Segment

Misc:

• Mo's algorithm