Pairwise alignment

Local alignment: The best possible matching substring or subsequence alignment between two strings—based on a substitution matrix and gap penalty function—allowing for gaps and mismatches within a specified region of the input sequences.
1. Dynamic programming solution¹: $O(nm)$ in terms of space and time. See vizualization ↗
Global alignment: The best possible alignment between two strings over their entire length.
1. Dynamic programming solution²: $O(nm)$ in terms of space and time. See vizualization ↗
2. Divide-and-conquer + dynamic programming solution³: $O(m)$ in terms of space and O(nm) time. See vizualization ↗
Longest common substring: The longest contiguous substring that appears in both strings.
1. Dynamic programming solution: $O(nm)$ in terms of space and time.
Longest common subsequence: The longest possible sequence of symbols that appears in the same order in both strings. See LCS distance.
1. Dynamic programming solution: $O(nm)$ in terms of space and time.
Dynamic time warping (DTW): The optimal warp path that minimizes the distance between sequences of varying length.
1. Dynamic programming solution⁴: $O(nm)$ in terms of space and time.
2. Space-time improved version of (1) via Hirschberg³ algorithm: Reduces space complexity to $O(m)$ .

Footnotes