DIRECTORY / algorithms
Algorithm Templates_
Notes from the workbench. Pick a file and dive in.
Esc
7 entries│subscribe --rss ↗
00algorithms/spfa.md1.3 KiB
Shortest Path Faster Algorithm
$ head -n 12 spfa.md
Shortest Path Faster Algorithm (SPFA) is an improved version of [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm), which uses a FIFO queue to maintain the relexing vertices. Time complexity: $O(|V| \times |E|)$. SPFA terminates only if there is no negative circle in the graph. And if we add some additional check (whether some node has been pushed into the queue more than N times) to check if there is a negative circle in the graph. Comparing with Dijksra, SPFA can work with negative distance but the time complexity of Dijkstra is more stable. ```c++#include <queue>#include <vector> using namespace std; 01algorithms/kmp.md1.5 KiB
KMP - Pattern Searching Algorithm
$ head -n 12 kmp.md
[KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) is a pattern searching algorithm.For given searching string $s$ and pattern string $p$, it pre-caculates a partial match table of $s$. Through thispartial match table, it can find the matching positions in $O(|s| + |p|)$ time. ## Template ```c++#include<string>#include<vector> using namespace std; 02algorithms/ac-auto.md4.2 KiB
AC Automaton Multi-Pattern Searching Algorithm
$ head -n 12 ac-auto.md
[AC](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm) is amulti-pattern searching algorithm. For a given set of pattern strings $S$, itpre-caculates a trie representing a state-machine for searching process. Andthe time complexity is $O(\sum_{s \in S} |s|)$. Here is an example of AC-automaton structure with 4 patterns (`she`, `shy`,`say`, `her`): ```dotdigraph { node [shape="record"]03algorithms/quick-sort.md1.3 KiB
Quick Sort Algorithm
$ head -n 12 quick-sort.md
[Quick Sort](https://en.wikipedia.org/wiki/Quicksort) is a sort algorithm of which thetime complexity is $O(n \times log(n))$. ## Template ```c++#include<vector> using namespace std; template<typename T>class quick_sort {04algorithms/trie.md1.2 KiB
Trie - Preffix Search Tree for Strings
$ head -n 12 trie.md
[Trie](https://en.wikipedia.org/wiki/Trie) is a kind of preffix search tree,by which we can map strings to any data type. For any given string $s$, thetime complexity of seeking is $O(|s|)$. Here is an example of trie structure with 4 strings (`her`, `say`, `she`, `shy`)inserted. ```dotstrict digraph { empty -> h[label="h"] h -> he[label="e"]05algorithms/leftist-tree.md2.0 KiB
Leftist Tree - Mergeable Heap
$ head -n 12 leftist-tree.md
[Leftist Tree](https://en.wikipedia.org/wiki/Leftist_tree) is a kind of mergeable heap. ## Template ```c++using namespace std; template<typename T>class leftist_tree { private: 06algorithms/fenwick-tree.md2.2 KiB
Fenwick Tree - Binary Indexed Tree
$ head -n 12 fenwick-tree.md
A [fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree) or binary indexedtree is a kind of data structure used to maintain the preffix sums of anordered list of numbers. ```dotdigraph { newrank = "true" node[shape = rect] C8 -> C4 C8 -> C6No matches. Try a shorter filename.
end of directory listing. ▉