In the paper two combinatorial problems for the set F_qⁿ of sequences of length n over the alphabet F_q={0,1,...,q-1} are considered. The maximum size N_q^-(n,t) of the set of common subsequences of length n-t and the maximum size N_q⁺(n,t) of the set of common supersequences of length n+t of two different sequences of F_qⁿ are found for any nonnegative integers n and t. The number N_q^-(n,t)+1 (respectively, N_q⁺(n,t)+1) is equal to the minimum number N of different subsequences of length n-t (supersequences of length n+t) of an unknown sequence X ∈ F_qⁿ which are sufficient for its reconstruction. Simple algorithms to recover X ∈ F_qⁿ from N_q^-(n,t)+1 of its subsequences of length n-t and from N_q⁺(n,t)+1 of its supersequences of length n+t are given.

sequence, subsequence, supersequence, common subsequence, reconstruction, algorithms.

Mathematical problems and theory of numerical methods