Аннотация:
Математическое ожидание $E$ длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин $m$ и $n$ этих слов и мощности алфавита $\alpha=|A|$.
При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова.
Указан вид приближённой формулы для $E (m,n,\alpha)$, позволяющий вычислять $E (m,n,\alpha)$ с погрешностью в $0.3$ процента для $64\leqslant m+n\leqslant 65536$ и $1<\alpha<129$.
Коэффициенты подобраны вручную и могут быть уточнены.
Ожидается, что формула справедлива для всех больших значений аргументов с той же относительной погрешностью.
Ключевые слова и фразы:сходство строк, выравнивание последовательностей, случайные общие подпоследовательности, LCS, метрика Левенштейна.