URI Online Judge | 1686

Palindromic Sequence

By Marcelo Galvão Póvoa, UNICAMP BR Brazil

Timelimit: 7

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
4 2
7 4
0 0