Задача
Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «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$ |
Код программы
|
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 |
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String q = bufferedReader.readLine(); int k = Integer.parseInt(q); String s = bufferedReader.readLine(); int l, r, flag=0, ans=0; for(int i=0; i<s.length()-k+1; i++) { flag=0; l=i; r=i+k-1; for(int j=0; j<k/2; j++) { if(s.charAt(l+j)!=s.charAt(r-j)){ flag=1; break; } } if(flag==0){ ans++; } } System.out.print(ans); } } |
Решение задачи
Мы рассматриваем все подстроки строки $s$ длины $k$ и проверяем, является ли каждая подстрока палиндромом. В случае положительного ответа, увеличиваем счетчик. Проверка, является ли каждая подстрока палиндромом, выполняется следующим образом: мы ставим указатели на противоположные концы подстроки, далее сравниваем элементы на которые указывают указатели и если они равны, одновременно сдвигаем указатели на один к центру этой подстроки. Продолжаем этот процесс до тех пор, пока указатели не «встретятся». Если на каком то этапе элементы не равны, прекращаем процесс с отрицательным ответом для этой подстроки. Если же указатели «встретились», то эта подстрока является палиндромом.