1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Christopher Boo Oct 17 at 4:43
  • 3
    \$\begingroup\$ Doesn't compile. Even with the appropriate includes and a set of using declarations, iPair<Node> makes no sense. \$\endgroup\$ – Toby Speight Oct 17 at 8:11
  • \$\begingroup\$ @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. \$\endgroup\$ – Toby Speight Oct 21 at 17:11