# Algorithm for building a string by appending and cloning substrings [closed]

I have a problem where I need to construct a given string from scratch for a minimum cost by either:

Appending a new character for a cost A

Appending a substring of my existing string for a cost B

E.g. for a string "abcabc" with a cost of A = 10, B = 11

a 10 ab 20 abc 30 abcabc 41

First I tried a greedy algorithm but it didn't give the optimal answer for this problem. I had the idea to use the dijkstra algorithm and a priority queue, so for each popped node I calculated the possibilities for A and B and pushed the new nodes back onto the queue. Since you can't change keys on the priority queue I use an int array ("visited") to keep track of the visited nodes.

However my solution isn't fast enough to finish 30000 char strings in 2 seconds so I wanted to ask for some pointers on how I could optimise/change my approach.

typedef pair<int, int> iPair;
int solve(string &s, int a, int b) {
priority_queue<iPair, iPair<Node>, greater<iPair>> pq;
int visited[s.size()];
for (int i = 0; i < s.size(); ++i)
visited[i] = -1;
pq.push(make_pair(a, 0));
iPair p;
while (!pq.empty()) {
p = pq.top();
pq.pop();
if (visited[p.second] == -1)
visited[p.second] = 1;
else
continue;
if (p.second == s.size() - 1)
break;

// Handle append costs
pq.push(make_pair(p.first + a, p.second + 1));

// Handle clone costs
int j;
int i = p.second;

if (s.size()  > 2*i + 2)
j = 2*i + 1;
else
j = s.size() - 1;

for (; j > i + 1; --j) {
if(s.substr(0, i+1).find(s.substr(i+1, j-i)) != string::npos) {
pq.push(make_pair(p.first + b, j));
break;
}
}
}
return p.current_cost;
}


As I say I'm looking for how I'm out of ideas how how to optimise this code and I'm not sure Dijkstra is even the right approach. I read up how A* search can speed up Dijkstra but I couldn't come up with an easy heuristic function.

• Dijkstra can work, but the reason your algorithm takes too long is in the clone costs part. You spend (O(n^2)) time finding the longest prefix from i that is a substring in s[0,i). Also, you might want to consider dynamic programming instead of Dijkstra. – Christopher Boo Oct 17 '19 at 4:43
• Doesn't compile. Even with the appropriate includes and a set of using declarations, iPair<Node> makes no sense. – Toby Speight Oct 17 '19 at 8:11
• @esperski, please make the necessary changes to fix the code. I don't think it requires much to turn it into working code so that we can re-open it for review. There's some issues (of varying subtlety) that I would like to help with. – Toby Speight Oct 21 '19 at 17:11