subsekvensseja

Subsekvensseja refers to subsequences in the context of sequences in mathematics and computer science. A subsequence of a sequence S = (s1, s2, ..., sn) is any sequence obtained by deleting zero or more elements without changing the relative order of the remaining elements. The empty sequence and the full sequence are subsequences.

A distinction: If the kept elements are consecutive, the subsequence is called a contiguous subsequence or substring in some contexts; subsequence does not require contiguity.

Counting and notation: A sequence of length n has 2^n subsequences, corresponding to the two options for each element: include or exclude. The number of subsequences of length k is C(n, k). The notion is a partial order: a subsequence T is a subsequence of S if it can be obtained by deletions.

Algorithms and examples: Checking whether a given T is a subsequence of S can be done by a single left-to-right scan in O(n) time. The longest subsequence by length among all subsequences is the LIS problem; efficient algorithms run in O(n log n). The longest common subsequence (LCS) problem seeks a longest subsequence common to two sequences and is solved by dynamic programming in O(mn) time, where m and n are the lengths of the two sequences.

Applications: subsekvensseja are used in DNA sequence analysis, text processing, diff and version control, and data compression. Variants include subsequences of strings and counting occurrences of a fixed subsequence, with several algorithms tailored to specific constraints.