Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени:	`500 мс`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Палиндромонойя

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.

Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.

Примеры

Входные данные	Результат работы
array	yes
iliya	no
anna<	yes<

Ссылки

Related Images:

Задача

Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «madam», «bob».
Определите, сколько палиндромов заданной длины $K$ содержит заданная строка $S$.

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

В первой строке содержится целое число $K$ ($2 \leqslant K \leqslant 200$), а во второй – заданная строка $S$, состоящая только из латинских букв, причем большие и малые буквы различаются (т.е. «Bob» — не палиндром). Длина $S$ от $1$ до $30000$ символов.

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

В единственной строке должно находиться количество различных палиндромов длины $K$, содержащихся в $S$ (т.е. являющихся последовательностями подряд идущих символов в $S$) (различными считаются палиндромы, начинающиеся с разных позиций в $S$).

Тесты

Входные данные	Выходные данные
$3$	$3$
$babcbab$
$1$	$5$
$abcde$
$4$	$0$
$aarreeds$
$5$	$3$
$aaaaaaa$
$3$	$0$
$CaccaC$

Код программы

String

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    string s;
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<s.size()-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

string s;

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<s.size()-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

C-String

#include <iostream>
#include <cstring>

using namespace std;

const int max_length=30001; 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    char s[max_length];
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<strlen(s)-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const int max_length=30001;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

char s[max_length];

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<strlen(s)-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

Решение задачи

Мы рассматриваем все подстроки строки $s$ длины $k$ и проверяем, является ли каждая подстрока палиндромом. В случае положительного ответа, увеличиваем счетчик. Проверка, является ли каждая подстрока палиндромом, выполняется следующим образом: мы ставим указатели на противоположные концы подстроки, далее сравниваем элементы на которые указывают указатели и если они равны, одновременно сдвигаем указатели на один к центру этой подстроки. Продолжаем этот процесс до тех пор, пока указатели не «встретятся». Если на каком то этапе элементы не равны, прекращаем процесс с отрицательным ответом для этой подстроки. Если же указатели «встретились», то эта подстрока является палиндромом.

Ссылки

Условие задачи на e-olymp
Код решения. String
Код решения. C-String

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: палиндромы

OCPC2021 B: Палиндромонойя

Палиндромонойя

Примеры

Ссылки

Related Images:

e-olymp 670. Поиск палиндромов

Задача

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

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

Тесты

Код программы

String

C-String

Решение задачи

Ссылки

Related Images: