問題タブ [subsequence]

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]

明らかに、この方法は完璧ではないか、この質問をするつもりはありませんが、アルゴリズムの問​​題を完全に理解できないようです。私はそれを長い間見てきたので、もうほとんど考えられませんが、それを修正する方法についてのアイデアは大歓迎です!

編集

複雑さは実際にはO(n*n*m)

Java では、インデックスが 10^5 桁の長さになる BigInteger のサブシーケンスを取得するにはどうすればよいですか。

例: BigInteger の長さは 10^5 です。インデックス 10^3 と 10^4 の間のサブシーケンスを見つける必要があります

リストの最初のインデックスから始まり、連続した順序でのみ下降する単調減少サブシーケンスの最後のインデックスを見つけられるようにしたいと考えています。たとえば、次のようなリストがあるとします。

x = [89, 88, 88, 88, 88, 87, 88]5サブシーケンスの最後の要素のインデックスであるため、返せるようにしたいと考えています[89, 88, 88, 88, 88, 87]。ここで、このサブシーケンスの各数値は単調減少し89、リストの最初のインデックスである から連続して減少します。

たとえば、次のようなリストがあったとしますx = [89, 87, 87, 86, 87]。0最初のインデックス (89) で始まり、連続して単調減少する (つまり、リストの次の数値は最初の数値から 2 ずつ減少する) 唯一の数値であるため、を返したいと思います。または、次のようなリストがある場合: 、リストの最初のインデックスから単調減少するシーケンスの唯一の部分であるため、x = [89, 90, 89, 88]戻りたいと思います。0

説明が難しくてすみません。助けてくれてありがとう！

コード (または次の問題のコードのスニペットまたは解決方法のヒント) が必要です。

文字列 s のサブシーケンスは、s から 1 つまたは複数の文字を削除することによって取得されます。文字列のサブ シーケンスのセットはs = abc、a, ab, ac, abc, b, bc, c,空の文字列 (すべての文字列のサブ シーケンス) になります。

s のすべての可能なサブ シーケンスを検索し、それらを辞書順に出力します。

これは私が出てきたものですが、機能していません:

結果：

出力: aab abc b bc c

期待される出力: a ab abc ac b bc c