RUS  ENG
Полная версия
ЖУРНАЛЫ // Журнал Сибирского федерального университета. Серия «Математика и физика» // Архив

Журн. СФУ. Сер. Матем. и физ., 2017, том 10, выпуск 1, страницы 71–74 (Mi jsfu526)

Эта публикация цитируется в 1 статье

A formula for the mean length of the longest common subsequence

[Формула для средней длины длиннейшей общей подпоследовательности]

Sergej V. Znamenskij

Ailamazyan Program Systems Institute of RAS, Peter the First, 4, Veskovo village, Pereslavl area, Yaroslavl region, 152021, Russia

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

Ключевые слова: длиннейшая общая подпоследовательность, математическое ожидание, длина LCS, численное моделирование, асимптотическая формула.

УДК: 004.412

Получена: 10.10.2016
Исправленный вариант: 10.11.2016
Принята: 20.12.2016

Язык публикации: английский

DOI: 10.17516/1997-1397-2017-10-1-71-74



Реферативные базы данных:


© МИАН, 2024