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

LZ77/LZ78