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 di erent ways of doing this.
In the rst 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 nd 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 nd 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 rst line of input will contain the given string. It can be assumed that the characters in the string are all small letters fa; : : : ; zg. 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 rst line of output should contain the answer for the rst 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 rst 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 le 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
