Постановка задачи

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

Например, если $a=$ «abc» и $b=$ «def», то $a\cdot b=$ «abcdef».
Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

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

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

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

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

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

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

Тесты

№	Входные данные	Выходные данные
1	abcabcabc	3
2	aaaaaaaaaa	10
3	ollollo	1
4	pjpjpjpj	4

Посмотреть работу программы на примере приведенных выше тестов можно на сайте ideone.

Решение

Описание решения

Получая строку str из потока ввода, вызываем функцию static public int StringPow(final String str) и передаем полученную строку в качестве входного параметра. Функция StringPow возвращает значение типа int — наибольшую степень строки, которую программа и передаст в поток вывода в качестве выходных данных.

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

Получив в качестве входного аргумента строку str, предположим внутри тела функции StringPow, что степень данной строки равна $1$ ( int pow = 1;) на тот случай, если бо́льшую степень найти не удастся.

Так как нужно найти число повторений подстроки минимального размера в строке str, будем проверять все подстроки размером от $1$ символа до size/2, где size — длина строки. Строка не может состоять из повторяющейся подстроки размером меньше $1$ или больше половины строки. Отсюда цикл for (int i=1; i<=size/2; i++).

Сразу будем отсеивать подстроки, из повторений которых строка не может состоять из-за несоответствия количества символов строки и подстроки ( if (size % i != 0) continue;). К примеру, строка длиной $8$ символов не может состоять из повторений подстроки длиной $3$ символа.

Запоминаем эту подстроку String sub1 = new String(str.substring(0, i));, а затем будем сравнивать с каждой следующей подстрокой такого же размера String sub2 = new String(str.substring(j, j+i)); во внутреннем цикле, предполагая перед этим, что мы нашли нужную нам подстроку ( boolean found = true;); если сверяемые подстроки различаются ( if (!sub1.equals(sub2))) — значит рассматриваемая подстрока sub1 искомой подстрокой не является. Прерываем действие внутреннего цикла и переходим к следующей подстроке, длиной на 1 символ больше. Если же строка полностью состоит из подстроки sub1 находим степень строки — число повторений подстроки в строке, иначе говоря, делим размер строки на размер подстроки ( pow = (size/i);).

Посмотреть решение задания можно на сайте e-olymp.