Lindon.md

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

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

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

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

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;
	}
}

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

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);
}