This section handles algorithms and data structures related to sequences. I also merged string algorithm in this section, because string is a specific instance of sequence.
pointer: maintain a subsequence by recording its left pointer and right pointer Both pointers will iteratively get updated while keeping the subsequence to be invariant to a specific property.
- Look up your sequence! : sometimes it is helpful to check whether your sequence is a well-known sequence
- Longest Increasing Subsequence (LIS) [c++]: $ O(n^2) $ solution or $ O(nlog(n)) $ solution
- Longest Common Subsequence (LCS) [wiki]: DP solution
- Maximum Subarray Problem: find subarray whose sum is the maximum (kadane)
Find matching patterns in a string. Introduction to algorithm has a chapter of good introduction regarding this topic.
String Matching Problems
- Rabin-Karp: hash the pattern into an integer (rolling hash), and find whether the hash appears in the string. pay attention to the spurious hits.
- Finite Automata: transforming the pattern into an automata
- KMP: build a transition table. When failing match
ithchar, transit to match table[i-1]
- Aho-Corasick: the multi-pattern version of KMP: transition table becomes a transition graph on top of Trie.
- Boyer-Moore: match pattern from right to left, shift the pattern when mismatched using (1) bad character rule (2) good suffix rule
- Manber & Myers: sort suffix array by increasing subsequence by the factor of 2. $O(nlog^2 n)$
Sequence Query Problems
RMQ (Range Minimum Query)
statement: query the minimum element within a given range on a sequence
- segment tree
- dynamic programming
- sparse table
- prefix code of loss less compression
- variable length code
- algorithm: recursively merge top two lowest frequent nodes to build the binary tree