Puppy and Palindromes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A recent survey suggested that almost everybody knows that a palindrome is a string which reads the same backwards as forwards. More recently, puppy Tuzik invented a brand-new concept: K-palindromes. A string is called a K-palindrome if it is possible to make it a usual palindrome by replacing at most K characters. For example, a string abb can be made a palindrome by replacing one character, the second b with an a. Please note, that according to the definition, a usual palindrome is a K-palindrome for any non-negative integer K.
Today, Tuzik was walking in a garden and came across a string S of N characters. Now, he wants to know the sum of the lengths of all substrings of S which are K-palindromes. Note that two substrings are considered to be different if they cover the different ranges of indices, even if they are equal as strings.
The first line of input contains an integer T denoting the number of test cases. Each of the next T lines contains a description of a separate test case.
The only line of the test case description contains two integers N and K followed by string S, all separated by single spaces. S consists of lowercase Latin characters only.
For each test case, output a single line containing one integer: the answer for the test case.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 105
- 0 ≤ K ≤ 5
Input: 2 7 0 abacaba 7 1 abacaba Output: 28 56
Test case 1:
- 7 0-palindromes with length 1 (just each character)
- 3 0-palindromes with length 3 (aba, aca, aba)
- 1 0-palindrome with length 5 (bacab)
- 1 0-palindrome with length 7 (abacaba) .
Test case 2:
- 7 1-palindromes with length 1 (just each character)
- 6 1-palindromes with length 2 (each substring with length 2)
- 5 1-palindromes with length 3 (each substring with length 3)
- 3 1-palindromes with length 5 (abaca,bacab, acaba)
- 1 1-palindrome with length 7 (abacaba) .
|Tags||constructive, cook67, hashing, palindromes, pavel1996|
|Time Limit:||7 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.