0

我正在阅读有关 geeksforgeeks 的一些动态编程文章，并遇到了最长公共子序列问题。我自己并没有提出指数朴素解决方案的实现，但是在在纸上解决问题的一些示例之后，我想出了我认为是成功实现O(n*m)版本的方法。然而，OJ 证明我错了。我的算法因输入字符串而失败：

  • "LRBBMQBHCDARZOWKKYHIDDQSCDXRJMOWFRXSJYBLDBEFSARCBYNECDYGGXXPKLORELLNMPAPQFWKHOPKMCO"
  • "QHNWNKUEWHSQMGBBUQCLJJIVSWMDKQTBXIXMVTRRBLJPTNSNFWZQFJMAFADRRWSOFSBCNUVQHFFBSAQXWPQCAC"

我对算法的思考过程如下。我想维护一个 DP 数组，其长度是输入字符串a中a较小的字符串长度。dpA[i]将是以 结尾的最长公共子序列a[i]。为此，我需要遍历a索引中的字符串0 => length-1并查看是否a[i]存在于b. 如果a[i]存在，b它将在 position pos。

  1. 第一个标记dp[i]好像1是dp[i]0
  2. 要知道这a[i]是对现有子序列的扩展，我们必须遍历a并找到与后面的值匹配的第一个i字符。让我们分别调用这些匹配值的索引。这个值保证是我们以前见过的值，因为我们已经涵盖了所有并填写了. 当我们找到第一个匹配项时，因为我们正在扩展前一个以. 冲洗重复。bposjka[0...i-1]dpA[0...i-1]dpA[i] = dpA[j]+1a[j]

显然这种方法并不完美，或者我不会问这个问题，但我似乎不太明白算法的问题。我一直在看它这么久，我几乎无法再考虑它，但任何关于如何修复它的想法将不胜感激！

int longestCommonSubsequenceString(const string& x, const string& y) {
  string a = (x.length() < y.length()) ? x : y;
  string b = (x.length() >= y.length()) ? x : y;

  vector<int> dpA(a.length(), 0);

  int pos;
  bool breakFlag = false;

  for (int i = 0; i < a.length(); ++i) {

    pos = b.find_last_of(a[i]);

    if (pos != string::npos) {

      if (!dpA[i]) dpA[i] = 1;

      for (int j = i-1; j >= 0; --j) {
        for (int k = pos-1; k >= 0; --k) {
          if (a[j] == b[k]) {
            dpA[i] = dpA[j]+1;
            breakFlag = true;
            break;
          }
          if (breakFlag) break;
        }
      }
    }

    breakFlag = false;
  }

  return *max_element(dpA.begin(), dpA.end());
}

编辑

我认为复杂性实际上可能是O(n*n*m)

4

0 回答 0