时间戳

首页 > 解决方案 > 通过附加和克隆子字符串来构建字符串的算法

c++ - 通过附加和克隆子字符串来构建字符串的算法

问题描述

我有一个问题，我需要以最低成本从头开始构造一个给定的字符串，方法是：

以成本 A 附加一个新角色

为成本 B 附加我现有字符串的子字符串

例如，对于成本为 A = 10、B = 11 的字符串“abcabc”

a 10 ab 20 abc 30 abcabc 41

首先我尝试了一个贪心算法，但它没有给出这个问题的最佳答案。我有使用 dijkstra 算法和优先级队列的想法，因此对于每个弹出的节点，我计算了 A 和 B 的可能性并将新节点推回队列中。由于您无法更改优先级队列上的键，因此我使用一个 int 数组（“已访问”）来跟踪已访问的节点。

但是我的解决方案不够快，无法在 2 秒内完成 30000 个字符字符串，所以我想请教一些关于如何优化/更改方法的指示。

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;
}

正如我所说，我正在寻找如何优化此代码的想法，我不确定 Dijkstra 是否是正确的方法。我阅读了 A* 搜索如何加速 Dijkstra，但我想不出一个简单的启发式函数。

标签： c++stringalgorithmoptimization

解决方案

这不是一个解决方案，而是一个可能的解决方案的前几个步骤。

理论解决方案如下：

  1. 让 S[i] 为 i 的子串的成本。字符。
  2. S[0] = 0，S[1] = A
  3. S[x] = S[x-1] + A 的最小值，或者任何 S[xk] + B 如果可以在 substring(0, xk) 中找到 substring(xk, x)

因此，我们需要根据数组中的先前值递增地计算 S[x] 值。计算 S[x-1]+A 很简单，但计算 S[xk]+B 的最小值非常昂贵，因为我们需要找到所有可能出现的子串。

理论上有可能 S[x]>S[x+k] （在某些 A、B 和 str 值中）

所以问题是我们如何优化子串的计算。

我认为某种独特的“最长公共子串”图可能会有所帮助，但是我还没有找到解决方案。如果我们为每个位置维护一个有序的成本列表并开始从最便宜的位置而不是从可能的最长子字符串开始查找可能的子字符串，则另一个优化。（添加子串的成本与子串的长度无关）

推荐阅读