0

geeksforgeeks に関する動的プログラミングの記事を読んでいて、Longest Common Subsequenceの問題に出くわしました。私は指数関数的な単純なソリューションの実装を自分で考え出すことはできませんでしたが、問題のいくつかの例を紙の上で解決した後、O(n*m)バージョンの実装が成功したと思われるものを思いつきました。しかし、OJ は私が間違っていることを証明しました。私のアルゴリズムは入力文字列で失敗します:

  • "LRBBMQBHCDARZOWKKYHIDDQSCDXRJMOWFRXSJYBLDBEFSARCBYNECDYGGXXPKLORELLNMPAPQFWKHOPKMCO"
  • "QHNWNKUEWHSQMGBBUQCLJJIVSWMDKQTBXIXMVTRRBLJPTNSNFWZQFJMAFADRRWSOFSBCNUVQHFFBSAQXWPQCAC"

アルゴリズムに対する私の思考プロセスは次のとおりです。長さが文字列の長さで、入力文字列の小さい方の DP 配列を維持したいと考えていaますa。dpA[i]で終わる最長共通サブシーケンスになりa[i]ます。これを行うにはa、インデックスから文字列を反復処理し、に存在する0 => length-1かどうかを確認する必要があります。存在する場合は、位置になります。a[i]ba[i]bpos

  1. dp[i]あたかも最初の1マークdp[i]0
  2. a[i]それが既存のサブシーケンスの拡張であることを知るには、 before の値と一致するa最初の文字を調べて見つける必要があります。これらの一致する値のインデックスをそれぞれ と と呼びましょう。この値は、 のすべてをカバーして記入したので、以前に見た値であることが保証されています。で終わる前のサブシーケンスを拡張しているため、最初の一致が見つかったとき。すすぎを繰り返します。ibposjka[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