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.
 Dynamic programming solution^{1}: $O(nm)$ in terms of space and time. See vizualization
 Global alignment: The best possible alignment between two strings over their entire length.
 Dynamic programming solution^{2}: $O(nm)$ in terms of space and time. See vizualization
 Divideandconquer + dynamic programming solution^{3}: $O(m)$ in terms of space and O(nm) time. See vizualization
 Longest common substring: The longest contiguous substring that appears in both strings.
 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.
 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.
 Dynamic programming solution^{4}: $O(nm)$ in terms of space and time.
 Spacetime improved version of (1) via Hirschberg^{3} algorithm: Reduces space complexity to $O(m)$.
Taken from: string2string: A Modern Python Library for StringtoString Algorithms
Footnotes

T. F. Smith and Michael S. Waterman. 1981. Identification of common molecular subsequences. Journal of molecular biology, 147 1:195–7 ↩

Saul B Needleman and Christian D Wunsch. 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3):443–453. ↩

Daniel S. Hirschberg. 1975. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6):341–343. ↩ ↩^{2}

Hiroaki Sakoe and Seibi Chiba. 1978. Dynamic programming algorithm optimization for spoken word recognition. IEEE transactions on acoustics, speech, and signal processing, 26(1):43–49. ↩