MAXimal | |
добавлено: 7 Sep 2008 14:40 Содержание [скрыть] Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвигаПонятие декомпозиции ЛиндонаОпределим понятие декомпозиции Линдона (Lyndon decomposition). Строка называется простой, если она строго меньше любого своего собственного суффикса. Примеры простых строк: , , , , , , . Можно показать, что строка является простой тогда и только тогда, когда она строго меньше всех своих нетривиальных циклических сдвигов. Далее, пусть дана строка . Тогда декомпозицией Линдона строки называется её разложение , где строки просты, и при этом . Можно показать, что для любой строки это разложение существует и единственно. Алгоритм ДюваляАлгоритм Дюваля (Duval's algorithm) находит для данной строки длины декомпозицию Линдона за время с использованием дополнительной памяти. Работать со строками будем в 0-индексации. Введём вспомогательное понятие предпростой строки. Строка называется предпростой, если она имеет вид , где — некоторая простая строка, а — некоторый префикс строки . Алгоритм Дюваля является жадным. В любой момент его работы строка S фактически разделена на три строки , где в строке декомпозиция Линдона уже найдена и уже больше не используется алгоритмом; строка — это предпростая строка (причём длину простых строк внутри неё мы также запоминаем); строка — это ещё не обработанная часть строки . Каждый раз алгоритм Дюваля берёт первый символ строки и пытается дописать его к строке . При этом, возможно, для какого-то префикса строки декомпозиция Линдона становится известной, и эта часть переходит к строке . Опишем теперь алгоритм формально. Во-первых, будет поддерживаться указатель на начало строки . Внешний цикл алгоритма будет выполняться, пока , т.е. пока вся строка не перейдёт в строку . Внутри этого цикла создаются два указателя: указатель на начало строки (фактически указатель на следующий символ-кандидат) и указатель на текущий символ в строке , с которым будет производиться сравнение. Затем будем в цикле пытаться добавить символ к строке , для чего необходимо произвести сравнение с символом . Здесь у нас возникают три различных случая:
РеализацияПриведём реализацию алгоритма Дюваля, которая будет выводить искомую декомпозицию Линдона строки : string s; // входная строка int n = (int) s.length(); int i=0; while (i < n) { int j=i+1, k=i; while (j < n && s[k] <= s[j]) { if (s[k] < s[j]) k = i; else ++k; ++j; } while (i <= k) { cout << s.substr (i, j-k) << ' '; i += j - k; } } АсимптотикаСразу заметим, что для алгоритма Дюваля требуется памяти, а именно три указателя , , . Оценим теперь время работы алгоритма. Внешний цикл while делает не более итераций, поскольку в конце каждой его итерации выводится как минимум один символ (а всего символов выводится, очевидно, ровно ). Оценим теперь количество итераций первого вложенного цикла while. Для этого рассмотрим второй вложенный цикл while — он при каждом своём запуске выводит некоторое количество копий одной и той же простой строки некоторой длины . Заметим, что строка является предпростой, причём её простые строки имеют длину как раз , т.е. её длина не превосходит . Поскольку длина строки равна , а указатель увеличивается по единице на каждой итерации первого вложенного цикла while, то этот цикл выполнит не более итераций. Худшим случаем является случай , и мы получаем, что первый вложенный цикл while всякий раз выполняет не более итераций. Вспоминая, что всего выводится символов, получаем, что для вывода символов требуется не более итераций первого вложенного while-а. Следовательно, алгоритм Дюваля выполняется за . Легко оценить и число сравнений символов, выполняемых алгоритмом Дюваля. Поскольку каждая итерация первого вложенного цикла while производит два сравнения символов, а также одно сравнение производится после последней итерации цикла (чтобы понять, что цикл должен остановиться), то общее число сравнений символов не превосходит . Нахождение наименьшего циклического сдвигаПусть дана строка . Построим для строки декомпозицию Линдона (мы можем это сделать за времени и памяти (если не выполнять конкатенацию в явном виде)). Найдём предпростой блок, который начинается в позиции, меньшей (т.е. в первом экземпляре строки ), и заканчивается в позиции, большей или равной n (т.е. во втором экземпляре). Утверждается, что позиция начала этого блока и будет началом искомого циклического сдвига (в этом легко убедиться, воспользовавшись определением декомпозиции Линдона). Начало предпростого блока найти просто — достаточно заметить, что указатель в начале каждой итерации внешнего цикла while указывает на начало текущего предпростого блока. Итого мы получаем такую реализацию (для упрощения кода она использует памяти, явным образом дописывая строку к себе): string min_cyclic_shift (string s) { s += s; int n = (int) s.length(); int i=0, ans=0; while (i < n/2) { ans = i; int j=i+1, k=i; while (j < n && s[k] <= s[j]) { if (s[k] < s[j]) k = i; else ++k; ++j; } while (i <= k) i += j - k; } return s.substr (ans, n/2); } Задачи в online judgesСписок задач, которые можно решить, используя алгоритм Дюваля:
|