A string is a sequence of characters. The kth power of a string w, denoted wk, is the string obtained by concatenating k copies of the string w. Formally, w0 is the empty string, and wk+1 = wk+w, where + denotes concatenation. Given a string s, it is required to measure how ‘far’ it is from the kth power of some string. There are different ways of doing this.
In the first part of the problem, you are only allowed to replace some characters in the string by others. Given a string s, and a number k, it is required to find the minimum number of replacements needed so that the resulting string is the kth power of some string. It can be assumed that the length of the given string is a multiple of k.
In the second part of the problem, you are also allowed to add characters at the end of the string, along with replacing existing characters. In this case, only the string is given and you have to find the minimum number of operations needed to change the string into a kth power for some k ≥ 2. An operation is either a replacement or addition of a character at the end. Note that k must be at least 2, otherwise the answer is always 0. Input/Output. The first line of input will contain the given string. It can be assumed that the characters in the string are all small letters {a,...,z}. The length of the string is at most 20000. The second line of input will contain a number k ≥ 2 that divides the length of the string.
The first line of output should contain the answer for the first part, the minimum number of replacements needed to convert the string into a kth power. The second output line should contain the answer for the second part. This should contain two numbers, the minimum number of operations required and the value of k such that the string is converted to a kth power. If there is more than one possible value of k, with the same number of operations, output the smallest one. You will get half credit if you do the first part correctly. Time limit is around 5 seconds for both parts. Sample Input/Output.
Input_1 Output_1
abaababa 3
4 2 2
Input_2 Output_2
abcabcab 4
2 1 3
Submission. Submit a single file named RollNo 4.cpp .
Homework. Can you do the same problem if more operations, like inserting a character at any position, and/or deletion of a character are allowed?
1
