私は、同じことを行う DP アプローチを説明した 2 つの文字列間の個別の共通サブシーケンスの数を数えることについて、この論文を読んでいました。現在、明確な共通サブシーケンスの数を見つけなければならない文字列が 3 つ以上ある場合、これとは異なるアプローチを取ることがあります。私が欲しいのは、このタスクが時間の複雑さで指数関数的よりも少ない時間で達成可能かどうか、そしてどのようにそれを行うことができるかということです?
質問する
1506 次
1 に答える
1
アルファベットのサイズkが で、m文字列のサイズが最大であるn場合 (すべての個々の数学演算が であると仮定するとO(1))、この問題は動的プログラミングで最大時間とメモリで解決できます。これらは厳密な境界ではなく、実際にはパフォーマンスとメモリはそれよりも大幅に優れているはずです。しかし、長い文字列を実際に使用すると、大きな整数演算が必要になり、数学演算が. それでも多項式です。O(k nm+1)O(k nm)O(1)
残念ながら紛らわしい文のトリックは次のとおりです。サブシーケンスの可能な長さごと、および各文字列から文字のコピーを 1 つ選択する方法のセットごとに、各文字列の最小式が選択された位置で終わる個別のサブシーケンスの数をリストする一連のテーブルを作成したいと考えています。スポット。これを行うと、これらすべての値の合計が最終的な答えになります。
これを行う方法の概要を次に示します (上記の説明を理解していなくても実行できます)。
文字列ごとに、その文字が次に出現する位置への遷移テーブル マッピング (文字列内の位置、文字) を作成します。テーブルは、最初の文字の前の位置 0 から開始する必要があります。-1 を使用して、文字列の末尾をはみ出すことができます。
持っている文字列の数と同じサイズの整数のリストを別の整数にマップするデータ構造を作成します。これは、各文字列の最短表現がその位置のセットで終了する固定長のサブシーケンスの数になります。
(0, 0, ..., 0) -> 1長さ 0 のサブシーケンスが 1 つあり、各文字列の最も短い表現が先頭で終わるという事実を表す唯一の値として挿入します。共通サブシーケンスの総数を 0 に設定します。
そのマップは空ではありませんが:
そのマップの値の合計を、共通のサブシーケンスの合計数に追加します。
データなしで、同じタイプの 2 番目のマップを作成します。
最初のマップのキーと値のペアごとに:
アルファベットで考えられる各文字について:
各文字列を取得し、位置を確認してから、その文字の次の位置を取得することにより、新しいキーとなる整数の新しいベクトルを構築します。もちろん、糸の端から外れたら、ループから抜け出します。
そのキーが 2 番目のマップにない場合は、値 0 で挿入します。
2 番目のマップのそのキーの値を、現在のマップの現在の値だけ増やします。(基本的に、この最小限の文字遷移があったサブシーケンスの数を追加します。)
2 番目のデータ構造を最初のデータ構造にコピーします。
すべての文字列に共通する個別のサブシーケンスの合計数が正しくなるはずです。
于 2013-06-27T18:28:02.843 に答える