404768: GYM101628 E Equivalent

Guga was bored, so he decided to read the dictionary and learned a new word:

• Palindrome: a word, phrase, or sequence that reads the same backward as forward.

madam, hannah, x e redivider are examples of palindromes.

Analyzing some words, Guga realized the most of them weren't palindromes and decided to create a new category called K-Palindrome, defined as follows:

• K-Palindrome: a word, phrase or sequence that, by substituting K letters, is equivalent to a palindrome.

For example, xyz is not a palindrome, but is a 1-Palindrome, because we can substitute the x with a z and obtain zyz. On the other hand, abcb is neither a palindrome nor a 1-Palindrome, but it is a 2-Palindrome, for we can substitute two letters and obtain a palindrome.

With this new definition, Guga was able to find many more words that satisfied it.

While researching on palindromes, Guga discovered the following problem: given a string S, how many continuous substrings of S are palindromes?

Intrigued, he decided to create an equivalent problem: given a string S and an integer K, how many continuous substrings of S are K-palindromes?

Guga thinks it's very easy to find a wrong answer to his problem with large strings, and want a computer program that solve it. Help Guga (:

Each test case consists of two lines.

The first line contains a string S (1 ≤ |S| ≤ 3000) composed only of lowercase letters, the string in which Guga wants to find the K-Palindromes.

The second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S.

The output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes.

ovo
1

6

ovo
0

4

By definition:

• Every K-Palindrome is also a K'-Palindrome, where K' > K.
• Every palindrome is a 0-palindrome.