Изменения
Нет описания правки
===Сложность===
Данный алгоритм работает за <tex>0(NlogN)</tex> действий и требует <tex>0(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения 1ого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>0(N+M)</tex> действий и требует <tex>0(N+M)</tex> памяти, где <tex>M</tex> - размер алфавита.
===Псевдокод===
Пусть N - количество символов во входной строке, M - количество символов в алфавите, k - номер исходной строки в матрице перестановок, s - входящая строка, count - массив для сортировки подсчетом, t - вектор обратного преобразования.
'''//считаем частоты символов'''
'''for i = 0..N count[i] = 0'''
'''for i = 0..N count[s[i]]++'''
'''//упорядочиваем символы, чтобы получить первый столбец исходной матрицы'''
'''//count[i] указывает на первую позицию символа i в первом столбце'''
'''sum = 0'''
'''for i = 0..N'''
''' sum = sum + count[i]'''
''' count[i] = sum - count[i]'''
'''//создаем вектор обратного преобразования'''
'''for i = 0..N'''
''' t[count[s[i]]]] = i'''
''' count[s[i]]++'''
'''//восстанавливаем исходный текст'''
'''j = t[x]'''
'''for i = 0..N'''
''' print(s[j])'''
''' j = t[j]'''
