Question

C++： A string construction problem defined as follows:

- You are given as input a target string

- Starting with an empty string, you add characters to it, until your new string is same as the target. You have two options to add characters to a string:

- You can append an arbitrary character to your new string, with cost x

- You can clone any substring of your new string so far, and append it to the end of your new string, with cost y

- For a given target, append cost x, and clone cost y, we want to know what the *cheapest cost* is of building the target string

For some simple examples:

- Target "aa", append cost 1, clone cost 2: the cheapest cost is 2:

- Start with an empty string, ""

- Append 'a' (cost 1), giving the string "a"

- Append 'a' (cost 1), giving the string "aa"

- Target "aaaa", append cost 2, clone cost 3: the cheapest cost is 7:

- Start with an empty string, ""

- Append 'a' (cost 2), giving the string "a"

- Append 'a' (cost 2), giving the string "aa"

- Clone "aa" (cost 3), giving the string "aaaa"

- Target "xzxpzxzxpq", append cost 10, clone cost 11: the cheapest cost is 71:

- Start with an empty string, ""

- Append 'x' (cost 10): "x"

- Append 'z' (cost 10): "xz"

- Append 'x' (cost 10): "xzx"

- Append 'p' (cost 10): "xzxp"

- Append 'z' (cost 10): "xzxpz"

- Clone "xzxp" (cost 11): "xzxpzxzxp"

- Append 'q' (cost 10) : "xzxpzxzxpq"

In the file `StringConstruction.h` implement a function `stringConstruction` that takes the target string, the clone cost, and the append cost (in that order), and returns the cheapest way of making the target string. It doesn't need to return *how* to do it, just the cost.

To test your code, TestStringCons.cpp contains some test cases.

Note: it will need to work for the largest of these target strings, which is 30,000 characters. the code will be ran on a modest desktop PC, and allowed 2 seconds.

StringConstruction.h file:

#ifndef STRINGCONSTRUCTION_H

#define STRINGCONSTRUCTION_H

#include <string>

using std::string;

// TODO: your code goes here:

// do not write or edit anything below this line

#endif

TestStringCons.cpp file:

#include "StringConstruction.h"

#include <iostream>

using std::cout;

using std::endl;

using std::ostream;

#include <vector>

using std::vector;

struct Testcase {

string target;

int appendCost;

int cloneCost;

int bestCost;

string notes;

};

ostream & operator<<(ostream & o, const Testcase & t) {

o << "Target string: " << t.target << "\n";

o << "Cost of appending an arbitrary character: " << t.appendCost << "\n";

o << "Cost of cloning a substring, and appending: " << t.cloneCost << "\n";

o << "Cheapest way to make the string should be: " << t.bestCost << "\n";

return o;

}

int main() {

int retval = 0;

vector<Testcase> testcases{

{"aa",1,2,2," Append 'a' (cost 1), append 'a' (cost 1)"},

{"aaaa",2,3,7," Append 'a' (cost 2), append 'a' (cost 2), clone 'aa' (cost 3)"},

{"xzxpzxzxpq", 10, 11, 71, " Append 'x' (cost 10), Append 'z' (cost 10), Append 'x' (cost 10), Append 'p' (cost 10), Append 'z' (cost 10),\n Clone 'xzxp' (cost 11), Append 'q' (cost 10)"}

};

for (size_t i = 0; i < testcases.size(); ++i) {

cout << "Testcase " << i << "\n";

cout << testcases[i];

cout << "\nRunning your function\n";

int costWas = stringConstruction(testcases[i].target, testcases[i].cloneCost, testcases[i].appendCost);

if (costWas == testcases[i].bestCost) {

cout << " -- Test passed, correct cost was returned\n\n\n";

} else {

cout << " -- Test failed, incorrect cost of " << costWas << " was returned\n";

cout << " To help your debugging, the cheapest way to make the string should be:\n";

cout << testcases[i].notes << "\n\n\n";

++retval;

}

}

string bigString = "abcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifpblgmbtmblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifpblgmbtmblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcqaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifpblgmbtmblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjoirmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifpblgmbtmblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipiblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifpblgmbtmblgmbaipfdmbcntdblgblgmbaipmbcntdblgblgmbaipcbcntdblgblgmbaipobacjodblgblgmbaiabcblgmbcntdblgblgmbaipmbcntdblgblgmbaipfdmbcqaipfdmbcntdblgblgmbaipmbcntdblgblgmbaiprtifbcntdblgblgmbaipmbcntdblgblgmbaip";

string doubleIt = bigString + bigString;

cout << "Big target string testcase, using a " << doubleIt.size() << " character test string. An excellent solution will complete in around a hundredth of a second.\n";

cout << "(Note -- if the program freezes at this point, Ctrl+C will stop it from running)\n";

int result = stringConstruction(doubleIt, 1235, 1234);

if (result == 59249) {

cout << "-- Correct cost of 59249 returned\n";

} else {

cout << "-- Incorrect cost of " << result << " returned, rather than 59249\n";

}

return retval;

}

Answer 1

#ifndef STRINGCONSTRUCTION_H

#define STRINGCONSTRUCTION_H

#include <string>
#include <iostream>


using std::string;
int stringConstruction(string target, int cloneCost, int appendCost) {
        string constructedString = "";
        int totalcost = 0;
        int lastIndex = 0;
                while (target != constructedString) {
                        int currLength = constructedString.length();
                        if (currLength == 0) {
                                totalcost += appendCost;
                                constructedString += target[0];
                                //std::cout << "append: " << target[0] << " cost: " << appendCost<<std::endl;
                                lastIndex = 1;
                        }
                        else {
                                bool cloned = false;
                                for (int i = currLength; i > 0; i--) {
                                        if (i*appendCost > cloneCost) {
                                                string sub = target.substr(lastIndex, i);
                                                if ((constructedString.find(sub, 0)) != string::npos) {
                                                        constructedString += sub;
                                                        cloned = true;
                                                        totalcost += cloneCost;
                                                        //std::cout << "clone: " << sub << " cost: " << cloneCost<<std::endl;
                                                        break;
                                                }
                                        }
                                }
                                if (!cloned) {
                                        constructedString += target[lastIndex];
                                        totalcost += appendCost;
                                        //std::cout << "append: " << target[lastIndex] << " cost: " << appendCost<<std::endl;
                                }
                                lastIndex = constructedString.length();
                        }
                }
        return totalcost;

}


#endif