MAXimal

добавлено: 7 Sep 2008 14:40
редактировано: 24 Aug 2011 18:36

Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига

Понятие декомпозиции Линдона

Определим понятие декомпозиции Линдона (Lyndon decomposition).

Строка называется простой, если она строго меньше любого своего собственного суффикса. Примеры простых строк: a, b, ab, aab, abb, ababb, abcd. Можно показать, что строка является простой тогда и только тогда, когда она строго меньше всех своих нетривиальных циклических сдвигов.

Далее, пусть дана строка s. Тогда декомпозицией Линдона строки s называется её разложение s = w_1 w_2 \ldots w_k, где строки w_i просты, и при этом w_1 \ge w_2 \ge \ldots \ge w_k.

Можно показать, что для любой строки s это разложение существует и единственно.

Алгоритм Дюваля

Алгоритм Дюваля (Duval's algorithm) находит для данной строки длины n декомпозицию Линдона за время O (n) с использованием O (1) дополнительной памяти.

Работать со строками будем в 0-индексации.

Введём вспомогательное понятие предпростой строки. Строка t называется предпростой, если она имеет вид t = w w w \ldots w \overline{w}, где w — некоторая простая строка, а \overline{w} — некоторый префикс строки w.

Алгоритм Дюваля является жадным. В любой момент его работы строка S фактически разделена на три строки s = s_1 s_2 s_3, где в строке s_1 декомпозиция Линдона уже найдена и s_1 уже больше не используется алгоритмом; строка s_2 — это предпростая строка (причём длину простых строк внутри неё мы также запоминаем); строка s_3 — это ещё не обработанная часть строки s. Каждый раз алгоритм Дюваля берёт первый символ строки s_3 и пытается дописать его к строке s_2. При этом, возможно, для какого-то префикса строки s_2 декомпозиция Линдона становится известной, и эта часть переходит к строке s_1.

Опишем теперь алгоритм формально. Во-первых, будет поддерживаться указатель i на начало строки s_2. Внешний цикл алгоритма будет выполняться, пока i < n, т.е. пока вся строка s не перейдёт в строку s_1. Внутри этого цикла создаются два указателя: указатель j на начало строки s_3 (фактически указатель на следующий символ-кандидат) и указатель k на текущий символ в строке s_2, с которым будет производиться сравнение. Затем будем в цикле пытаться добавить символ s[j] к строке s_2, для чего необходимо произвести сравнение с символом s[k]. Здесь у нас возникают три различных случая:

  • Если s[j] = s[k], то мы можем дописать символ s[j] к строке s_2, не нарушив её "предпростоты". Следовательно, в этом случае мы просто увеличиваем указатели j и k на единицу.

  • Если s[j] > s[k], то, очевидно, строка s_2 + s[j] станет простой. Тогда мы увеличиваем j на единицу, а k передвигаем обратно на i, чтобы следующий символ сравнивался с первым символом s_2.

  • Если s[j] < s[k], то строка s_2+s[j] уже не может быть предпростой. Поэтому мы разбиваем предпростую строку s_2 на простые строки плюс "остаток" (префикс простой строки, возможно, пустой); простые строки добавляем в ответ (т.е. выводим их позиции, попутно передвигая указатель i), а "остаток" вместе с символом s[j] переводим обратно в строку s_3, и останавливаем выполнение внутреннего цикла. Тем самым мы на следующей итерации внешнего цикла заново обработаем остаток, зная, что он не мог образовать предпростую строку с предыдущими простыми строками. Осталось только заметить, что при выводе позиций простых строк нам нужно знать их длину; но она, очевидно, равна j-k.

Реализация

Приведём реализацию алгоритма Дюваля, которая будет выводить искомую декомпозицию Линдона строки 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;
	}
}

Асимптотика

Сразу заметим, что для алгоритма Дюваля требуется O (1) памяти, а именно три указателя i, j, k.

Оценим теперь время работы алгоритма.

Внешний цикл while делает не более n итераций, поскольку в конце каждой его итерации выводится как минимум один символ (а всего символов выводится, очевидно, ровно n).

Оценим теперь количество итераций первого вложенного цикла while. Для этого рассмотрим второй вложенный цикл while — он при каждом своём запуске выводит некоторое количество r \ge 1 копий одной и той же простой строки некоторой длины p = j-k. Заметим, что строка s_2 является предпростой, причём её простые строки имеют длину как раз p, т.е. её длина не превосходит r p + p - 1. Поскольку длина строки s_2 равна j-i, а указатель j увеличивается по единице на каждой итерации первого вложенного цикла while, то этот цикл выполнит не более r p + p - 2 итераций. Худшим случаем является случай r = 1, и мы получаем, что первый вложенный цикл while всякий раз выполняет не более 2 p - 2 итераций. Вспоминая, что всего выводится n символов, получаем, что для вывода n символов требуется не более 2 n - 2 итераций первого вложенного while-а.

Следовательно, алгоритм Дюваля выполняется за O (n).

Легко оценить и число сравнений символов, выполняемых алгоритмом Дюваля. Поскольку каждая итерация первого вложенного цикла while производит два сравнения символов, а также одно сравнение производится после последней итерации цикла (чтобы понять, что цикл должен остановиться), то общее число сравнений символов не превосходит 4 n - 3.

Нахождение наименьшего циклического сдвига

Пусть дана строка s. Построим для строки s+s декомпозицию Линдона (мы можем это сделать за O (n) времени и O (1) памяти (если не выполнять конкатенацию в явном виде)). Найдём предпростой блок, который начинается в позиции, меньшей n (т.е. в первом экземпляре строки s), и заканчивается в позиции, большей или равной n (т.е. во втором экземпляре). Утверждается, что позиция начала этого блока и будет началом искомого циклического сдвига (в этом легко убедиться, воспользовавшись определением декомпозиции Линдона).

Начало предпростого блока найти просто — достаточно заметить, что указатель i в начале каждой итерации внешнего цикла while указывает на начало текущего предпростого блока.

Итого мы получаем такую реализацию (для упрощения кода она использует O (n) памяти, явным образом дописывая строку к себе):

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

Список задач, которые можно решить, используя алгоритм Дюваля: