KDoubleSubstrings
SRM 321 · 2006-10-02 · by Mike Mirzayanov
Problem Statement
A k-double string is a non-empty string consisting of two equal length halves, where the first half differs from the second half at no more than k positions. For example, "contestcontest", "oopoop" and "aa" are 0-double strings. "contestkontest" is a 1-double string, and "poorpork", "artbat", and "yesyep" are 2-double strings. Obviously, all 0-double strings are also 1-double strings, all 1-double strings are also 2-double strings, etc.
You will be given a
If the same string exists in several different positions, count it as many times as it exists. Also, k-double substrings can overlap. See the examples for more details.
Constraints
- str will contain between 1 and 5 elements, inclusive.
- Each element of str will contain between 1 and 50 characters, inclusive.
- Each element of str will contain only lowercase letters ('a'-'z').
- k will be between 0 and 100, inclusive.
{"aa"}
0
Returns: 1
"aa" is the only 0-double substring.
{"aaaa"}
0
Returns: 4
There are four substrings of even length and all of them are 0-double strings.
{"contest", "kontest"}
1
Returns: 14
Each pair of consecutive letters form a 1-double substring and the whole string form one more 1-double substring.
{"abacaba", "d", "abacaba"}
1
Returns: 34
{"areyouready"}
2
Returns: 18
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class KDoubleSubstrings with a public method int howMuch(vector<string> str, int k) · 60 test cases · 2 s / 256 MB per case