Журнал СФУ. Математика и физика / Формула для средней длины длиннейшей общей подпоследовательности

Полный текст (.pdf)
Номер
Журнал СФУ. Математика и физика. 2017 10 (1)
Авторы
Знаменский, Сергей В.
Контактная информация
Знаменский, Сергей В.: Институт программных систем РАН Петра Первого, 4, Переславльский район, Ярославская обл., 152021 Россия
Ключевые слова
longest common subsequence; expected value; LCS length; simulation; asymptotic formula; длиннейшая общая подпоследовательность; математическое ожидание; длина LCS; численное моделирование; асимптотическая формула
Аннотация

Математическое ожидание E длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от мощности алфавита jAj и длин m и n этих слов. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Предъявлено простое выражение для E( ; m; n) при фиксированных и m + n

Страницы
71–74
Статья в архиве электронных ресурсов СФУ
https://elib.sfu-kras.ru/handle/2311/30296