Задача
Обозначим через [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[/latex] = [latex]a^{n}[/latex] для некоторой строки [latex]a[/latex].
Тесты
Входные данные | Выходные данные |
---|---|
abcabc gcdgcd gcgcgc gggggg hhhh |
2 2 3 6 4 |
BbbbBbbbBbbb dogdogdog aaaaaaaa cstring |
3 3 8 1 |
Код программы (c-string)
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 |
#include <iostream> #include <cstring> using namespace std; unsigned int cstringpow(const char *s) { unsigned int answer = 1; const unsigned int size = strlen(s); for (unsigned int i = 1; i < size/2+1; ++i) { /* Ищем предполагаемую степень для ответа, которая обязательно является делителем длины строки. */ if (size % i == 0) { bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна for (int j = 0; j < size-i; j += i) { //сравниваем блоки строки if (strncmp(s+j, s+j+i, i) != 0) { not_broken = 0; break; } } if (not_broken) { //Если предполагаемая степень строки оказалась верной, возвращаем её. answer = size/i; break; } } } return answer; } int main() { char s[1000010]; //Выделяем память для строк while (cin >> s) cout << cstringpow(s) << endl; return 0; } |
Решение задачи (c-string)
Из условия следует, что степень строки определяется максимальным числом одинаковых подстрок. В таком случае степень строки является одним из делителей длины этой строки, и очевидно, что максимальная степень строки будет обратно пропорциональна максимальной длине подстроки.
Для решения поставленной задачи используем функцию
cstringpow, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной
size (с использованием счётчика
i в цикле), в которую было предварительно была сохранена длина строки, полученная функцией
strlen. Числа, которые будут получатся из выражения
size/i, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.
Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем, используя функцию
strncmp, сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения
size/i будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, а следовательно её степень равна [latex]1[/latex].
Код программы (string)
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 45 |
#include <iostream> #include <string> using namespace std; unsigned int stringpow(const string &s) { unsigned int answer = 1; const unsigned int size = s.size(); for (unsigned int i = 1; i < size/2+1; ++i) { /* Ищем предполагаемую степень для ответа, которая обязательно является делителем длины строки. */ if (size % i == 0) { bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна for (int j = 0; j < size-i; j += i) { //сравниваем блоки строки if (s.compare(j, i, s, j+i, i) != 0) { not_broken = 0; break; } } if (not_broken) { //Если предполагаемая степень строки оказалась верной, возвращаем её. answer = size/i; break; } } } return answer; } int main() { string s; //Выделяем переменную класса "строка" while (cin >> s) cout << stringpow(s) << endl; return 0; } |
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 45 46 47 48 49 50 51 52 53 54 |
import java.util.*; import java.io.*; public class Main { public static int stringpow(String s) { int answer = 1; int size = s.length(); for(int i = 1; i < size/2+1; ++i) { /* Ищем предполагаемую степень для ответа, которая обязательно является делителем длины строки. */ if (size % i == 0) { boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна String current = s.substring(0, i); for(int j = 0; j < size-i; j += i) { //сравниваем блоки строки if (!(current.equals(s.substring(j+i, j+2*i)))) { not_broken = false; break; } } if (not_broken) { answer = size/i; break; } } } return answer; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); String S; //Выделяем переменную класса "строка" while(in.hasNextLine()) { S = in.nextLine(); out.println(stringpow(S)); } out.flush(); } } |
Решение задачи (string)
Решение задачи с использованием класса string аналогично. Единственное отличие — замена функций strlen и strncmp, предназначенных для работы с c-string, на эквивалентные им методы класса string size и compare.
Ссылки
- Условие задачи на www.e-olymp.com;
- Код решения с использованием c-string (C++) и 100% результат в системе www.e-olymp.com;
- Код решения с использованием string (C++) и 100% результат в системе www.e-olymp.com;
- Код решения с использованием String (Java) и 100% результат в системе www.e-olymp.com;
Принято