Задача взята с сайта e-olymp.com
Условие задачи
Будем говорить, что символьная строка имеет период [latex]k[/latex], если она может быть образована путем объединения одной или нескольких одинаковых строк длиной [latex]k[/latex]. Например, строка «[latex]abcabcabcabc[/latex]» имеет период [latex]3[/latex], так как она может быть образована путём объединения [latex]4[/latex]-х строк «[latex]abc[/latex]». Она также имеет период [latex]6[/latex] (объединение двух строк «[latex]abcabc[/latex]») и [latex]12[/latex] (сама строка «[latex]abcabcabcabc[/latex]»).
Напишите программу определяющую наименьший период заданной строки.
Входные данные
В первой строке задано количество тестовых случаев [latex]N[/latex] во входных данных. Каждый тестовый случай размещен в отдельной строке и содержит не более [latex]80[/latex] символов без пробелов.
Выходные данные
Вывести для каждого тестового случая искомое значение наименьшего периода строки. Разные тестовые случаи должны быть разделены пустой строкой.
Тесты
Входные данные | Выходные данные |
2 HoHoHo mama |
2
2 |
2 abcdefg abcabcabc |
7
3 |
3 b bbb bbbbb |
1
1 1 |
Код программы
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; int strPeriod(char *str){ int period; period = strlen(str); // for(int i=1; i<=(strlen(str)/2); i++){ /* разбиваем строку на подстроки*/ int j; for(j=0; j<strlen(str)-i; ){ /* ограничение номера символа, чтобы не выйти за границы строки*/ if(str[j] == str[j+i]){ j++; } else{ break; } } if(j == (strlen(str) - i)){ /* если цикл дошел до конца строки - период найден*/ period = i; break; } } return period; } int main() { const int n = 81; int tests; cin >> tests; cin.ignore(1, ' '); /* пропуск символа перехода на новую строку*/ char *str = new char[n]; for(int j=0; j<tests; j++){ cin.getline(str, n); cout << strPeriod(str); if(j != tests - 1){ cout << endl << endl; } } return 0; } |
Засчитанное решение на e-olymp.com
Решение
Строка длины [latex]s[/latex] может быть образована подстрокой, длина которой не превышает половины длины строки. Следовательно, период лежит в промежутке [latex]\left [ 1;s/2 \right ][/latex], либо равен длине строки. Последовательно разбивая строку на подстроки длиной от [latex]1[/latex] до [latex]s/2[/latex], проверяем равны ли они между собой. Если такие подстроки не нашлись, то период равен длине строки.
Хорошо. Зачтено.