# 0x313 Sequence

## Sequence

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.

### Strategies

• Two 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

### Subsequence Problems

• 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)

### String Problems

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 ith char, 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

#### Suffix Array

• 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
• LCA

### Compression

#### Huffman Code

• prefix code of loss less compression
• variable length code
• algorithm: recursively merge top two lowest frequent nodes to build the binary tree