Palindromic Sequence
By Marcelo Galvão Póvoa, UNICAMP 
Brazil
By Marcelo Galvão Póvoa, UNICAMP Brazil
Given a string s[1..N], we define a palindromic sequence of length p and displacement d (1 <= p <= d) as a sequence of k (k >= 1) disjoint substrings of s (each of which is a palindrome of length p) distant d characters from each other.
More formally, it can be written as the following sequence of disjoint substrings of s : A= (s[i..i+p-1], s[i+d..i+d+p-1], s[i+2d..i+2d+p-1], ...), where each element of A is a palindrome of length p. Recall that a string is called a palindrome if it reads the same forwards and backwards.
The value of a palindromic sequence is the total number of characters from string s it uses (i.e., if the sequence has k palindromes of length p, its value is k*p). Given a fixed displacement value D, calculate the largest value of a palindromic sequence contained in a string S.
Each test case is described using two lines. The first line contains two integers N and D (1 <= N <=10^5), 1 <= D <=10^5) representing respectively the length of the string S and the required displacement value. The next line contains the string S of length N consisting only of lowercase letters.
The last test case is followed by a line containing two zeros.
For each test case output a line with the maximum value of a palindromic sequence with displacement D in string S.
| Sample Input | Sample Output |
|
5 1 |
5 |