По заданной строке s найти самую короткую строку t, такую ​​что t ^ m = s

Question

Для заданной строки s найдите самую короткую строку t, такую ​​что t ^ m = s.

Примеры:

s="aabbb" => t="aabbb"
s="abab"  => t = "ab"

Как быстро это можно сделать?

Конечно, наивно, что для каждого m делится | s |, я могу попробовать, если подстрока (s, 0, | s | / m) ^ m = s.

Можно найти решение за время O (d (| s |) n), где d (x) - число делителей s. Можно ли сделать это более эффективно?

Answer 1

Это проблема вычисления периода строки. Алгоритм последовательного сопоставления строк Кнута, Морриса и Пратта - хорошее место для начала.Это в документе под названием «Быстрое сопоставление с образцом в строках» от 1977 года.

Если вы хотите с ним поразмышлять, то посмотрите статью «Поиск всех периодов и начальных палиндромов строки параллельно»Breslauer и Galil в 1991 году. Из их аннотации:

Представлен оптимальный алгоритм CRCW-PRAM времени O (log log n) для вычисления всех периодов строки.Предыдущие параллельные алгоритмы вычисляют период, только если он короче половины длины строки.Этот алгоритм может использоваться для одновременного нахождения всех начальных палиндромов строки и границ процессора.Оба алгоритма являются самыми быстрыми из общего алфавита.Мы находим нижнюю границу для нахождения палиндромов путем модификации ранее известной нижней границы для нахождения периода строки [3].Когда доступно p процессоров, границы становятся \ Theta (dnpe + log log d1 + p = ne 2p).

Answer 2

Мне действительно нравится эта вещь, называемая z-алгоритмом: http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm

Для каждой позиции вычисляется самая длинная подстрока, начиная с нее, которая также является префиксом всей строки. (в линейном времени, конечно).

a   a   b   c   a   a   b   x   a   a   a   z
    1   0   0   3   1   0   0   2   2   1   0

Учитывая эту "z-таблицу", легко найти все строки, которые могут быть возведены в целое. Просто проверьте все позиции, если pos+z[pos] = n.

В нашем случае:

a   b   a   b
    0   2   0

Здесь pos = 2 дает вам 2+z[2] = 4 = n, следовательно, самая короткая строка, которую вы можете использовать, имеет длину 2.

Это даже позволит вам найти случаи, когда совпадает только префикс из возведенной в степень строки, например:

a   b   c   a
    0   0   1

Здесь (abc)^2 можно сократить до вашей исходной строки. Но, конечно, если вам не нужны такие совпадения, просто перейдите через делители.

Answer 3

Да, вы можете сделать это за O(|s|) время.

Вы можете искать строку «target» длиной n в строке «source» длины m за O(n+m) времени.Постройте решение на основе этого.

Пусть и источник, и цель будут s.Дополнительным ограничением является то, что 1 и любые позиции в источнике, которые не делят |s|, не являются действительными начальными позициями для матча.Конечно, поиск сам по себе всегда будет неудачным.Но если есть частичное совпадение, и вы достигли конца строки источника, то у вас есть решение исходной проблемы.

Answer 4

модификация Бойера-Мура могла бы обработать это в O (n), где n - длина s

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm