Изменения

Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра". Как несложно посчитать сложность данного алгоритма <tex> 0(N^3logN) </tex>, также он требует <tex>0(N^2)</tex> памяти.Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции.Теперь если определить порядок получения символов 1ого столбца из символов последнего, то полученные значения будут являться вектором обратного преобразования. Для получения исходной строки надо выписать символы из преобразованной строки в порядке, соответствующему данному вектору, начиная с номера, содержащегося в исходных данных. Рассмотрим данный алгоритм на том же примере.{| | {| border="1" |0||а||&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;||р||9 |- |1||а||||д||7 |- |2||а|| ||a||0 |- |3||а|| ||к||8 |- |4||а|| ||р||10 |- |5||б|| ||a||1 |- |6||б|| ||a||2 |- |7||д|| ||a||3 |- |8||к|| ||a||4 |- |9||р|| ||б||5 |- |10||р|| ||б||6 |} | || | {| border="1" |9||&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;||2 |- |7||||5 |- |0||||6 |- |8||||7 |- |10||||8 |- |1||||9 |- |2||||10 |- |3||||1 |- |4||||3 |- |5||||0 |- |6||||4 |}|}