A Formula for the Mean Length of the Longest Common Subsequence
View/ Open:
URI (for links/citations):
https://elib.sfu-kras.ru/handle/2311/30296Author:
Znamenskij, Sergej V.
Знаменский, Сергей В.
Date:
2016-12Journal Name:
Журнал Сибирского федерального университета. Математика и физика. Journal of Siberian Federal University. Mathematics & Physics;2017 10 (1)Abstract:
The expected value E of the longest common subsequence of letters in two random words is considered
as a function of the = jAj of alphabet and of words lengths m and n. It is assumed that each letter
independently appears at any position with equal probability. A simple expression for E( ; m; n) and its
empirical proof are presented for fixed and m + n. High accuracy of the formula in a wide range of
values is confirmed by numerical simulations Математическое ожидание E длиннейшей общей подпоследовательности букв двух случайных
слов рассматривается как функция от мощности алфавита jAj и длин m и n этих слов. При
этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой
позиции слова. Предъявлено простое выражение для E( ; m; n) при фиксированных и m + n