Сходство между сжатыми строками: различия между версиями

Рисунок 1. Таблица динамического программирования для строк arcpbt и asbqcu, разбитая на 9 блоков. Для одного из блоков, например, B, из E и F вычисляются только нижняя строка C и крайний правый столбец D

Строка S кодируется по длине серии, если она описывается упорядоченной последовательностью пар (a, i), часто обозначаемых как «a'», каждая из которых состоит из символа алфавита, a, и целого числа, i. Каждая пара соответствует длине серии в S, состоящей из i последовательных вхождений a. Например, строка aaabbbbbaccccbb может быть закодирована в виде a3b4a1c4b2 или, что эквивалентно, (a, 3) (b, 4) (a, 1) (c, 4) (b, 2). Пусть A и B – две строки длиной n и m, соответственно, A0 и B0 – закодированные при помощи длин серий строки A и B, а n0 и m0 – длины A0 и B0, соответственно.