Concepts318
Category
Sliding Window
Sliding window is a technique that moves a contiguous segment (window) across an array or string while maintaining some running information like sum, count, or max.
Ternary Search
Ternary search finds the maximum or minimum of a unimodal function on a line by probing two interior points and discarding one third of the interval each step.
Binary Search on Answer
Binary Search on Answer turns an optimization problem into a yes/no decision problem over a monotonic answer space.
Two Pointers
Two pointers is a pattern where two indices move through a sequence in a coordinated, usually monotonic way to avoid unnecessary work.
Binary Search
Binary search quickly finds targets or boundaries in sorted or monotonic data by halving the search interval each step.
Aho-Corasick - DP Applications
Aho–Corasick (AC) turns a set of forbidden patterns into a finite automaton that lets you process or generate strings while tracking whether any pattern appears.
Li Chao Tree
A Li Chao tree maintains a set of lines y = m x + b and answers minimum (or maximum) value queries at a given x in O(log C) time, where C is the numeric range of x.
Palindromic Tree (Eertree)
A Palindromic Tree (Eertree) stores every distinct palindromic substring of a string as a node and can be built online in linear time.
Suffix Automaton - Advanced Usage
A suffix automaton (SAM) is a compact DFA that captures all distinct substrings of a string and supports many advanced queries in linear time.
Suffix Automaton
A suffix automaton (SAM) is the minimal deterministic finite automaton that recognizes all substrings of a string, built online in O(n) time and space.
Aho-Corasick Automaton
Aho–Corasick is a trie with failure links that finds all occurrences of many patterns in a single pass over the text.
Suffix Array - LCP Array Applications
The LCP (Longest Common Prefix) array, built alongside a suffix array, unlocks fast solutions to problems like longest repeated substring, number of distinct substrings, and longest common substring.