c++ - 指定された 2 つの文字列の親文字列

Question

2 つの文字列が与えられた場合、与えられた文字列が文字列のサブシーケンスになるように、長さが最小の文字列を見つける必要があります。つまり、一部の文字を削除すると指定された文字列になるような文字列を見つける必要があります。ブルートフォースとLCSを考えていましたが無駄でした。

12345 と 11234 は 112345 WWA になり、WWS には応答 WWAS があります

LCS はかなりメモリ効率が悪く (DP のもの)、総当りは幼稚です。私は何をすべきか？

Answer 1

おそらく、インデルを優先するために、 Needleman-Wunschと高いミスマッチ ペナルティを使用してグローバル アラインメントを行うことができます。最後に、一致する位置から文字を取得し、次に挿入された文字のいずれかから文字を取得して、配置を「親文字列」にマージします。

WW-A
||  
WWS-

WWSA

または：

-12345
 ||||
11234-

112345

メモリはO(nm)ですが、変更によりO(min(n,m)) に絞り込まれます。

Answer 2

標準ライブラリには、目的に役立つ明確に定義されたアルゴリズムがあります。

set_union ();

条件は、入力範囲をソートする必要があることです。