Постановка задачи
Обозначим через [latex]a\cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].
Например, если [latex]a=[/latex] «abc» и [latex]b=[/latex] «def», то [latex]a\cdot b=[/latex] «abcdef».
Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:
[latex]a^{0}=[/latex] «» (пустая строка)
[latex]a^{n+1}=a\cdot a^{n}[/latex]
По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].
Входные данные:
Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.
Выходные данные:
Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].
Тесты
| № |
Входные данные |
Выходные данные |
| 1 |
abcabcabc |
3 |
| 2 |
aaaaaaaaaa |
10 |
| 3 |
ollollo |
1 |
| 4 |
pjpjpjpj |
4 |
Посмотреть работу программы на примере приведенных выше тестов можно на сайте ideone.
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import java.util.*; class task6 { static public int StringPow(final String str) { int size = str.length(); int pow = 1; for (int i=1; i<=size/2; i++) { if (size % i != 0) continue; String sub1 = new String(str.substring(0, i)); boolean found = true; for (int j = i; j < size; j+=i) { String sub2 = new String(str.substring(j, j+i)); if (!sub1.equals(sub2)) { found = false; break; } } if (found) { pow = (size/i); break; } } return pow; } static public void main (String[] argv) { String str; Scanner in = new Scanner(System.in); while (in.hasNext()) { str = in.nextLine(); System.out.println(StringPow(str)); } in.close(); } } |
Описание решения
Получая строку
str из потока ввода, вызываем функцию
static public int StringPow(final String str) и передаем полученную строку в качестве входного параметра. Функция
StringPow возвращает значение типа
int — наибольшую степень строки, которую программа и передаст в поток вывода в качестве выходных данных.
Минимальной степенью строки может быть число [latex]1[/latex] — в том случае, если в заданной строке [latex]s[/latex] нет повторяющихся подстрок. Максимальной же степенью строки может быть количество символов, из которых строка состоит — в том случае, если строка состоит из одного повторяющегося символа. В этом случае этот символ и будет считаться повторяющейся подстрокой.
Получив в качестве входного аргумента строку
str, предположим внутри тела функции
StringPow, что степень данной строки равна [latex]1[/latex] (
int pow = 1;) на тот случай, если бо́льшую степень найти не удастся.
Так как нужно найти число повторений подстроки минимального размера в строке
str, будем проверять все подстроки размером от [latex]1[/latex] символа до
size/2, где
size — длина строки. Строка не может состоять из повторяющейся подстроки размером меньше [latex]1[/latex] или больше половины строки. Отсюда цикл
for (int i=1; i<=size/2; i++).
Сразу будем отсеивать подстроки, из повторений которых строка не может состоять из-за несоответствия количества символов строки и подстроки (
if (size % i != 0) continue;). К примеру, строка длиной [latex]8[/latex] символов не может состоять из повторений подстроки длиной [latex]3[/latex] символа.
Запоминаем эту подстроку
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.
