| Author | Znamenskij, Sergej V. | en |
| Author | Знаменский, Сергей В. | ru_RU |
| Accessioned Date | 2016-12-16T06:36:03Z | |
| Available Date | 2016-12-16T06:36:03Z | |
| Issued Date | 2016-12 | |
| URI (for links/citations) | https://elib.sfu-kras.ru/handle/2311/30296 | |
| 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 | en |
| Abstract | Математическое ожидание E длиннейшей общей подпоследовательности букв двух случайных
слов рассматривается как функция от мощности алфавита jAj и длин m и n этих слов. При
этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой
позиции слова. Предъявлено простое выражение для E( ; m; n) при фиксированных и m + n | ru_RU |
| Language | en | en |
| Publisher | Сибирский федеральный университет. Siberian Federal University | en |
| Subject | longest common subsequence | en |
| Subject | expected value | en |
| Subject | LCS length | en |
| Subject | simulation | en |
| Subject | asymptotic formula | en |
| Subject | длиннейшая общая подпоследовательность | ru_RU |
| Subject | математическое ожидание | ru_RU |
| Subject | длина LCS | ru_RU |
| Subject | численное моделирование | ru_RU |
| Subject | асимптотическая формула | ru_RU |
| Title | A Formula for the Mean Length of the Longest Common Subsequence | en |
| Alternative Title | Формула для средней длины длиннейшей общей подпоследовательности | ru_RU |
| Type | Journal Article | |
| Type | Published Journal Article | |
| Contacts | Znamenskij, Sergej V.: Ailamazyan Program Systems Institute of RAS Peter the First, 4, Veskovo village, Pereslavl area, Yaroslavl region, 152021 Russia; svz@latex.pereslavl.ru | en |
| Contacts | Знаменский, Сергей В.: Институт программных систем РАН Петра Первого, 4, Переславльский район, Ярославская обл., 152021 Россия | ru_RU |
| Pages | 71–74 | |
| Journal Name | Журнал Сибирского федерального университета. Математика и физика. Journal of Siberian Federal University. Mathematics & Physics;2017 10 (1) | en |
