optimisation of the algorithm for constructing a string given costs to operations

The problem is that you’re making the decision to clone greedily. Let’s look at a case where the append cost is 2 and the clone cost is 3. If you process the string aabaaaba, you’ll append aab, clone aa, and clone aba, whereas the best solution is to append aaba and clone it.

The fix is dynamic programming, specifically, to build an array of the cost to make each prefix of the target string. To fill each entry, take the min of (append cost plus previous entry, clone cost plus cost for the shortest prefix that can be completed with one clone). Since the clone cost is constant, the array is nondecreasing, and therefore we don’t need to check all of the possible prefixes.

Depending on the constraints you may need to construct a suffix array/longest common prefix array (using e.g., SA-IS) to identify all of the best clones quickly. This will run in time o(n²) for sure (quite possibly O(n), but there are enough moving parts that I don’t want to claim that).

This Python is too slow but gets the right answer on the large test case:

def best_clone(s):
    j = len(s) - 1
    while s[j:] in s[:j]:
        j -= 1
    return j + 1


def construction_cost(s, append_cost, clone_cost):
    table = [0]
    for i in range(len(s)):
        cost = table[i] + append_cost
        j = best_clone(s[: i + 1])
        if j <= i:
            cost = min(cost, table[j] + clone_cost)
        table.append(cost)
    return table[len(s)]

If the limit of your ambitions is quadratic, then we can put the Z function for string matching to good use.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>

using Cost = unsigned long long;

// Adapted from https://cp-algorithms.com/string/z-function.html
std::vector<std::size_t> ZFunction(std::string_view s) {
  std::size_t n = s.length();
  std::vector<std::size_t> z(n);
  for (std::size_t i = 1, l = 0, r = 0; i < n; i++) {
    if (i <= r) {
      z[i] = std::min(r - i + 1, z[i - l]);
    }
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
      z[i]++;
    }
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

std::size_t BestClone(std::string_view s) {
  std::string r{s};
  std::reverse(r.begin(), r.end());
  auto z = ZFunction(r);
  std::size_t best = 0;
  for (std::size_t i = 0; i < z.size(); i++) {
    best = std::max(best, std::min(z[i], i));
  }
  return s.length() - best;
}

Cost ConstructionCost(std::string_view s, Cost append_cost, Cost clone_cost) {
  std::vector<Cost> costs = {0};
  for (std::size_t j = 0; j < s.length(); j++) {
    std::size_t i = BestClone(s.substr(0, j + 1));
    if (i <= j) {
      costs.push_back(
          std::min(costs.back() + append_cost, costs[i] + clone_cost));
    } else {
      costs.push_back(costs.back() + append_cost);
    }
  }
  return costs.back();
}

int main() {
  std::string s;
  while (std::cin >> s) {
    std::cout << ConstructionCost(s, 1234, 1235) << '\n';
  }
}

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top