В настоящее время я пытаюсь выяснить, является ли данный массив, который является перестановкой чисел от 1 до n, массивом суффиксов какой-либо двоичной строки.
Например, для n = 3, A = {2, 1, 3} является действительным, поскольку существует двоичная строка [101] с [01] <[1] <[101] (с использованием лексикографического упорядочения). Однако {2, 3, 1} не является допустимым суффиксным массивом, так как нет двоичной строки, для которой выполняется лексикографический порядок. </p>
Мой текущий подход просто перечисляет все двоичные строки длины n и проверяет, правильно ли упорядочен массив суффиксов w.r.t. каждая строка Это, очевидно, довольно медленно, поскольку в O (n) нужно проверить 2 ^ n двоичных строк-кандидатов.
Очевидный подход к решению проблемы такого рода заключается в поиске сходства в допустимых массивах суффиксов, однако до сих пор я мог вывести только одно свойство:
Если A является допустимым массивом суффиксов для двоичной строки, то перед префиксом A с 1 и увеличением всех значений A также получается действительный массив суффиксов.
Однако это свойство не помогает мне с массивами суффиксов, которые не начинаются с 1, при попытке их проверить.