1632
правки
Изменения
м
<code>
</code>
<code>
</code>
rollbackEdits.php mass rollback
Вот примерная реализация этого алгоритма. Здесь массив <tex>\mathtt{alphabet}</tex> хранит количество символов перед символом <tex>S[i]</tex>, <tex>N</tex> {{---}} длина строки <tex>S</tex>.
'''list<int>''' mtf(N):
'''list<int>''' result(N)
помещаем символ S[i] в начало алфавита
'''return''' result
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>M</tex> {{---}} размер алфавита, <tex>N</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N\log M)</tex>.
Пусть дан алфавит размером <tex>M</tex> и строка <tex>S</tex> длиной <tex>N</tex>. Запомним для каждого символа алфавита свой ключ. Изначально <tex>\mathtt{keys}['a'] = 0</tex>, <tex>\mathtt{keys}['b'] = 1</tex>, <tex>\dots</tex> , <tex>\mathtt{keys}['z'] = M-1</tex>. Соединим все вершины в дерево по ключу.
'''list<int>''' mtf(N):
'''list<int>''' result(N)
merge(cur, tree) <font color=darkgreen> //Объединяем нашу вершину и дерево по ключу</font color=darkgreen>
'''return''' result
Функция <tex>\mathtt{findanswer}</tex> считает ответ так: если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу.
== Обратное преобразование ==
Пусть даны строка <tex>S = 1222100</tex> и исходный алфавит ''"ABC"''. Символ с номером <tex>1</tex> в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером <tex>2</tex> в алфавите {{---}} это 'AC', поэтому 'AC' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
{| class ="wikitable"
| 0 || 16 || 4/5 || 0
|-
| 1 || 2 1 || 1/10 20 || 10110
|-
| 2 || 1 || 1/20 || 110111
|-
| 3 || 1 2 || 1/20 10 || 11110
|}
