Задача
Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «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
|
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 |
#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
|
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 |
#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