Минимальный циклический сдвиг

Задача: “Дается строка S. Длина S не превышает 1e5. Необходимо найти минимальный в лексикографическом порядке циклический сдвиг строки S”.

1.Полиномиальные хеш-функции.
По мотивам презентации Александра Скиданова

Рассмотрим строку S = “abcdabb”
h(L) – полиномиальная хеш-функция от префикса строки S длины L.




h(0) = h(“”)        = 0
h(1) = h(“a”)       = a
h(2) = h(“ab”)      = a*x¹ + b
h(3) = h(“abc”)     = a*x² + b*x¹ + c
h(4) = h(“abcd”)    = a*x³ + b*x² + c*x¹ + d
h(5) = h(“abcda”)   = a*x⁴ + b*x³ + c*x² + d*x¹ + a
h(5) = h(“abcdab”)  = a*x⁵ + b*x⁴ + c*x³ + d*x² + a*x¹ + b
h(5) = h(“abcdabb”) = a*x⁶ + b*x⁵ + c*x⁴ + d*x³ + a*x² + b*x¹ + b

Рекурсивно полиномиальную хеш-функцию h(L) можно выразить так:


H(a,b)- полиномиальная хеш-функция от подстроки S в интервале [a,b)

Следовательно можно получать полиномиальные хеш-функции от любой подстроки S за O(1).

Пусть len – длина строки S.
Возвращаемся к первоначальной задачи. Чтобы найти минимальный циклический сдвиг строки S:
1) Модифицируем исходную строчку S = S + S.
2) Считаем полиномиальную хеш-функцию h(L) для всех префиксов строки S.
3) На текущем шаге наилучший ответ на поставленную задачу – это подстрока строки S длины len, начинающаяся c позиции best = 0.
4) Последовательно перебираем все возможные начальные позиции cur в интервале [1,len)
5) Бинарным поиском подбираем длину общего префикса для наилучшего текущего ответа, начинающегося с позиции best, и кандидата на это место, начинающегося с позиции cur.
6) Сравниваем первые различные символы двух образцов. Если у текущего кандидата на этой позиции стоит символ с меньшим кодом, тогда обновляет наилучший ответ.

1. typedef unsigned long long UINT;
2. int min_cycle_shift(char *s, int init_len) {
3.   UINT *hash = new UINT[2*init_len];
4.   hash[0] = 0;
5.   for (int i=1;i<2*init_len;++i)
6.     hash[i] = x * hash[i-1] + s[i-1];
7.  
8.   int bst_pos = 0;
9.   for (int cur_pos = 1; cur_pos < init_len; ++cur_pos) {
10.     int l = 0, r = init_len-1, res = 0;
11.     while (l <= r) {
12.       int len = (l + r) >> 1;
13.       UINT hash_bst = hash[bst_pos + len] - hash[bst_pos] * _pow[len];
14.       UINT hash_cur = hash[cur_pos + len] - hash[cur_pos] * _pow[len];
15.       if (hash_bst == hash_cur) {
16.         res = len;
17.         l = len + 1;
18.       }
19.       else {
20.         r = len - 1;
21.       }
22.     }
23.     if (s[bst_pos + res] > s[cur_pos + res])
24.       bst_pos = cur_pos;
25.   }
26.   delete[] hash;
27.   return bst_pos + 1;
28. }

* This source code was highlighted with Source Code Highlighter.

Сложность данного решения:

P.S: В качестве x нужно использовать небольшое простое число. Например 11.
P.S.S: Все вычисления ведутся без модульной арифметики. Поэтому интервал возможных значений полиномиальной хеш-функции равен 2⁶⁴.

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

Все что нужно - написано на e-maxx’e. Приведу просто фрагмент кода, решающую ту же самую задачу.

1. // s уже равна s+s
2. int min_cycle_shift(char *s, int len) {
3.   int i = 0, ans = 0;
4.   while (i < len/2) {
5.     ans = i;
6.     int k = i, j = i+1;
7.     while (j < len && s[k] <= s[j]) {
8.       if (s[k] < s[j])
9.         k = i;
10.       else
11.         ++k;
12.       ++j;
13.     }
14.     while (i<=k)
15.       i += j - k;
16.   }
17.   return ans + 1;
18. }

* This source code was highlighted with Source Code Highlighter.

Сложность данного решения: