e-olymp 1078. The line degree

Задача взята с сайта e-olymp.com.

Условие

Обозначим через $a*b$ конкатенацию строк $a$ и $b$.

Например, если $a = «abc»$ и $b = «def»$, то $a*b = «abcdef»$.

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

$a^0 = «»$ (пустая строка)
$a^{n+1} = a*a^n$

По заданной строке $s$ необходимо найти наибольшее значение $n$, для которого $s = a^n$ для некоторой строки $a$.

Входные данные

Каждый тест состоит из одной строки $s$, содержащей печатные (отображаемые) символы. Строка $s$ содержит не менее одного и не более миллиона символов.

Выходные данные

Для каждой входной строки $s$ вывести в отдельной строке наибольшее значение $n$, для которого $s = a^n$ для некоторой строки $a$.

Тесты:

Входные данные Выходные данные
$abcabc$
$gcdgcd$
$gcgcgc$
$gggggg$
$hhhh$
$2$
$2$
$3$
$6$
$4$
$BbbbBbbbBbbb$
$dogdogdog$
$aaaaaaaa$
$cstring$
$3$
$3$
$8$
$1$

Код на Haxe:

Ход решения:

Из условия следует, что степень строки определяется максимальным числом одинаковых подстрок. В таком случае степень строки является одним из делителей длины этой строки, и очевидно, что максимальная степень строки будет обратно пропорциональна максимальной длине подстроки.
Для решения поставленной задачи используем функцию $cstringpow$, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной $size$ (с использованием счётчика $i$ в цикле), в которую было предварительно была сохранена длина строки, полученная из свойства $lenght$. Числа, которые будут получатся из выражения $size/i$, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.

Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения $size/i$ будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, следовательно, её степень равна $1$.

Ссылки:

Оригинальное решение: cpp.mazurok.com.
Рабочий код для тестирования на try.haxe.org: Try Haxe !

Latest posts by Владислав Козачков (see all)

2 thoughts on “e-olymp 1078. The line degree

Добавить комментарий