|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||85||32||18||26.471%|
A palindrome is a word which reads the same backward or forward. For example, abba, akasaka, and glenelg are palindromes. Also we can define θ-palindrome as follows: given a real number θ (0 < θ ≤ 1), a string w is a θ-palindrome if it can be decomposed as concatenation of three strings, that is, w = uvuR where uR is the reversal of u and θ ≤ 2|u|/|w|. For example, if θ = 0.8 and w = ababa, then w is a θ-palindrome as u = ab, v = a, and θ ≤ 2|u|/|w|. Note that v may be an empty string whose length is zero but u cannot be an empty string.
A string may be represented as concatenation of θ-palindromes. For example, assume that θ = 0.5 and w = abbaaba. It is a θ-palindrome itself as u = ab, v = baa and θ ≤ 2|u|/|w|=4/7. When θ = 0.6, it can be written as concatenation of abba and aba. It is evident that both are θ-palindromes.
Given a string w and a real number θ, you write a program which computes the minimal number of θ-palindromes such that their concatenation is w.
Your program is to read from standard input. The input consists of two lines. The first line contains three integers, n, k, and l (1 ≤ n ≤ 10,000, 1 ≤ k ≤ l ≤ 100) where n is the length of the string w and θ = k/l.The next line contains the string w in English lowercase.
Your program is to write to standard output. Print an integer representing the minimal number of θ-palindromes such that their concatenation is w. If such θ-palindromes do not exist, print 0.
7 1 2 abbaaba
7 3 5 abbaaba
7 4 5 abcdefg