4086 - Find Palindrome Spread

Created by Luis Manuel Díaz Barón
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Given a string S composed by lowercase letters of the Latin alphabet, you must find the number of characters in S, that don't belong to any palindrome substring of S of at least 2 <= K <= |S| letters. A palindrome string is one string that is read in the same way, from left to right and from right to left.
;jsessionid=3747A33E9ADAE7C7C56FE06E69A8757C
Dada una cadena S compuesta por letras minúsculas del alfabeto latino, debe encontrar el número de caracteres en S que no pertenecen a ninguna subcadena palindrómica de S de al menos 2 <= K <= |S| letras. Una cadena palindrómica es una cadena que se lee de la misma manera de izquierda a derecha y de derecha a izquierda.
Given a string S composed by lowercase letters of the Latin alphabet, you must find the number of characters in S, that don't belong to any palindrome substring of S of at least 2 <= K <= |S| letters. A palindrome string is one string that is read in the same way, from left to right and from right to left.
;jsessionid=3747A33E9ADAE7C7C56FE06E69A8757C

Input specification

The first line of input contains two space separated integers N (1 <= N <= 10^6) and K (2 <= K <= N); N is the length of the string. The second line contains the string S.
La primera línea de entrada contiene dos enteros separados por espacio N (1 <= N <= 10 ^ 6) y K (2 <= K <= N); N es la longitud de la cadena. La segunda línea contiene la cadena S.
The first line of input contains two space separated integers N (1 <= N <= 10^6) and K (2 <= K <= N); N is the length of the string. The second line contains the string S.

Output specification

The only line of output contains the number of characters in S, that don't belong to any palindrome substring of S of at least K letters.
;jsessionid=3747A33E9ADAE7C7C56FE06E69A8757C
La única línea de salida debe contener el número de caracteres en S, que no pertenecen a ninguna subcadena palindrómica de S de al menos K letras.
;jsessionid=3747A33E9ADAE7C7C56FE06E69A8757C
The first line of input contains two space separated integers N (1 <= N <= 10^6) and K (2 <= K <= N); N is the length of the string. The second line contains the string S.

Sample input

10 3
asdbaabasd

Sample output

5

Hint(s)

In the example test are two palindromes of length equal to or greater than K:

asd[baab]asd
asdba[aba]sd

So the only characters not belonging to any palindrome of length greater than K, are the ones in positions: 1, 2, 3, 9, 10.
En el caso de ejemplo hay dos palíndromos de longitud mayor o igual que K:

asd[baab]asd
asdba[aba]sd

Así que los únicos caracteres que no pertenecen a ningún palíndromo de longitud mayor que K son los que están en las posiciones: 1, 2, 3, 9, 10.
In the example test are two palindromes of length equal to or greater than K:

asd[baab]asd
asdba[aba]sd

So the only characters not belonging to any palindrome of length greater than K, are the ones in positions: 1, 2, 3, 9, 10.