Нахождение повторяющейся последовательности в конце последовательности чисел

Вы можете использовать скользящий хеш для достичь линейной временной сложности и пространственной сложности O (1) (я думаю, что это так, поскольку я не верю, что у вас может быть бесконечная повторяющаяся последовательность с двумя частотами, которые не кратны друг другу).

Алгоритм: вы просто сохраняете два скользящих хэша, которые расширяются следующим образом:

                       _______  _______  _______
                      /       \/       \/       \
...2038975623895769874883301010883301010883301010
                      .        .        .      ||
                      .        .        .    [][]
                      .        .        .  [ ][ ]
                      .        .        .[  ][  ]
                      .        .       [.  ][   ]
                      .        .     [  . ][    ]
                      .        .   [    .][     ]
                      .        . [      ][      ]
                      .        [       ][       ]

Продолжайте делать это для всей последовательности. Первый проход будет обнаруживать только повторения, повторяющиеся 2*n раз для некоторого значения n. Однако это не наша цель: наша цель при первом проходе — обнаружить все возможные периоды, что и происходит. По мере прохождения последовательности, выполняющей этот процесс, мы также отслеживаем все относительно простые периоды, которые нам нужно будет проверить позже:

periods = Set(int)
periodsToFurthestReach = Map(int -> int)

for hash1,hash2 in expandedPairOfRollingHashes(sequence):
    L = hash.length
    if hash1==hash2:
        if L is not a multiple of any period:
            periods.add(L)
            periodsToFurthestReach[L] = 2*L
        else L is a multiple of some periods:
            for all periods P for which L is a multiple:
                periodsToFurthestReach[P] = 2*L

После этого процесса у нас есть список всех периодов и того, как далеко они продвинулись. Наш ответ, вероятно, самый дальний, но мы проверяем все остальные периоды на повторение (быстро, потому что мы знаем периоды, которые мы проверяем). Если это сложно с вычислительной точки зрения, мы можем оптимизировать, сокращая периоды (которые перестают повторяться) по мере того, как мы проходим по списку, очень похоже на решето Эратосфена, сохраняя приоритетную очередь того, когда мы в следующий раз ожидаем повторения периода.

В конце мы еще раз проверяем результат, чтобы убедиться, что не было коллизии хэшей (вряд ли она есть, заносим в черный список и повторяем).

Здесь я предположил, что ваша цель состояла в том, чтобы минимизировать неповторяющуюся длину, а не давать повторяющийся элемент, который можно было бы дополнительно учесть; вы можете изменить этот алгоритм, чтобы найти все другие сжатия, если они существуют.

Итак, ninjagecko дал хороший рабочий ответ на поставленный мною вопрос. Большое спасибо! Тем не менее, я нашел более эффективный, математически обоснованный способ сделать конкретный случай, который я рассматриваю, то есть написать выражение в закрытой форме для разложения непрерывной дроби квадратичного иррационального числа. Очевидно, что это решение будет работать только для этого конкретного случая, а не для общего случая, о котором я спрашивал, но я подумал, что было бы полезно разместить его здесь, если у других возникнет аналогичный вопрос.

По сути, я вспомнил, что квадратичное иррациональное число сокращается тогда и только тогда, когда его разложение в непрерывную дробь является чисто периодическим — то есть оно повторяется с самого начала без каких-либо ведущих членов.

Когда вы работаете над разложением числа x в непрерывную дробь, вы в основном устанавливаете x_0 равным x, а затем формируете свою последовательность [a_0; a_1, a_2, a_3, ...] путем определения a_n = floor(x_n) и x_(n+1) = 1/(x_n - a_n). Обычно вы просто продолжаете это, пока не достигнете желаемой точности. Однако для наших целей мы просто запускаем этот метод до тех пор, пока x_k не станет приведенным квадратичным иррациональным числом (что происходит, если оно больше 1, а его сопряженное число находится в диапазоне от -1 до 0). Как только это происходит, мы знаем, что a_k — это первый член нашего повторяющегося блока. Затем, когда мы находим x_(k+m+1) равным x_k, мы знаем, что a_(k+m) — это последний член в нашем повторяющемся блоке.

Поиск справа:

• делает a_n == a_n-1
• делает (a_n,a_n-1) == (a_n-2,a_n-3)
• ...

Это явно O (m ^ 2). Единственная доступная граница, по-видимому, заключается в том, что m ‹ n/2, так что это O (n ^ 2)

Это приемлемо для вашего приложения? (Мы делаем вашу домашнюю работу за вас, или здесь действительно существует реальная проблема?)

На этой странице перечислены несколько хороших алгоритмов обнаружения циклов и представлена ​​реализация алгоритма на C.

Рассмотрим последовательность после того, как она повторилась несколько раз. Это закончится, например. ...12341234123412341234. Если вы возьмете повторяющуюся часть строки непосредственно перед последним циклом повторений, а затем продвинете ее на длину этого цикла, вы обнаружите, что у вас есть длинное совпадение между подстрокой в ​​конце последовательности и та же подстрока сдвинулась влево на расстояние, малое по сравнению с ее длиной.

И наоборот, если у вас есть строка, в которой a[x] = a[x + k] для большого числа x, то у вас также есть a[x] = a[x + k] = a[x + 2k] = a [x + 3k]... поэтому строка, совпадающая с самой собой при перемещении на короткое расстояние по сравнению с ее длиной, должна содержать повторы.

Если вы посмотрите на http://en.wikipedia.org/wiki/Suffix_array, вы увидите что вы можете построить список всех суффиксов строки в отсортированном порядке за линейное время, а также массив, который сообщает вам, сколько символов каждый суффикс имеет общего с предыдущим суффиксом в отсортированном порядке. Если вы ищете запись с наибольшим значением this, это будет мой кандидат на строку, идущую ..1234123412341234, а расстояние между начальными точками двух суффиксов скажет вам длину, на которой последовательность повторяется. (но на практике какой-то скользящий хеш-поиск, например http://en.wikipedia.org/wiki/Rabin-Karp может быть быстрее и проще, хотя существуют вполне программируемые алгоритмы массива суффиксов линейного времени, такие как «Простое построение массива суффиксов линейной работы» Карккайнена и Сандерса).

Предположим, вы применяете этот алгоритм, когда количество доступных символов равно 8, 16, 32, 64, .... 2 ^ n, и вы, наконец, находите повтор в 2 ^ p. Сколько времени вы потратили впустую на предыдущих этапах? 2 ^ (p-1) + 2 ^ (p-2) + ..., что в сумме составляет около 2 ^ p, поэтому повторные поиски являются только постоянными накладными расходами.