понедельник, 19 декабря 2011 г.

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

Задача: “Дается строка 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*x1 + b
h(3) = h(“abc”)     = a*x2 + b*x1 + c
h(4) = h(“abcd”)    = a*x3 + b*x2 + c*x1 + d
h(5) = h(“abcda”)   = a*x4 + b*x3 + c*x2 + d*x1 + a
h(5) = h(“abcdab”)  = a*x5 + b*x4 + c*x3 + d*x2 + a*x1 + b
h(5) = h(“abcdabb”) = a*x6 + b*x5 + c*x4 + d*x3 + a*x2 + b*x1 + 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: Все вычисления ведутся без модульной арифметики. Поэтому интервал возможных значений полиномиальной хеш-функции равен 264.

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.

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

Комментариев нет:

Отправить комментарий