文字列に挿入して回文に変換するための最小文字数

Question

文字列を回文に変換するのに必要な最小限の挿入数を見つける必要があります。注：挿入は、任意の場所、末尾、または内で行うことができます。それが最後であった場合は、hereという質問があります。

1. は、文字列をS1とする：
   は、だから私は、これはこの単純なトリックでO(N**2)時間で行うことができることを見出しました。それを逆にする。それをs2とする。長さがlであるとします。
2. ここで、s1とs2の最も長い共通部分シーケンスを見つけます。その長さをxとしましょう。
3. 答えはl-xです。

たとえば、s1 = abcdaとします。従ってs2 = adcba。長さは5です。最も長い共通部分シーケンスは、長さが3のabaです。したがって、挿入の最小数は5-3 = 2であり、結果の文字列はadcbcdaです。

しかし、私はそれの背後にある論理を理解できません。誰でもそれがなぜ私にそれを説明することができますか？

さらに、O(N)解決策がありますか？

Answer 1

O(N)ソリューションがあるかどうかわかりませんが、逆の場合と比較すると、回文型の部分列が見つかります。その後、ペアにされていない文字がl-xになります。 （文字のペアは、単語の真中に鏡がある場合、その反射として考えることができます（例：ab | ba）。その後、挿入するだけで画像が完成します。

まず、2つの文字列に共通する（最大）部分列を見つけるにはどうすればよいですか？私たちはs1とs2（S1の逆）間の最長共通部分列（LCS）を見つけるためにしようとすると、それはここ https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

をそれを参照してください見つけるための多項式アルゴリズムがあり、私たちは実際には最初s1との最初の半分の間のLCSを見つけますs2の半分、s1の後半およびs2の後半。

S1 = abcddzac

のでS2 = cazddcbaと仮定する。ここではabcdとcazd（前半）の比較とdzacとdcba（後半）の比較としてそれを見ることができます。それらが互いに逆であることを除けば、両方の比較が同じであることがわかります。したがって、それらの連結は回文でなければなりません。したがって、s1とs2のlcsは回文でなければなりません。

lcs（ad|da）の長さが4になると、対称性（b、c、z、c）を破る文字が4つ増えます。次に、それらのそれぞれに1つの文字を挿入して対称、すなわち回文を作る。私たちは、LCSの中間点として、当社の中間点を設定し、我々は

S1 = ad|d BC zのa Cを持っているので、我々はその中間点から二つにS1を破ることを考えると、我々はDから2に棒のようにそれを破ります| Dと我々はで終わる：彼らは同じになるように
d Z a C
d CB a

今、私たちは単にLCSの文字の間を埋めます。次のように我々の場合の手順は次のとおり

d Z a C
d CB a

d Z a C
d ZCB a

d ZC a C
d ZCB a

d ZCB a C
d ZCB a

d ZCB a C
d ZCB a C


今、私たちは同じポイントからそれを壊れないよう、私たちは
C a bcz dd ZCB aを持っていますcはパリンドロームです。

注：cddcもldcですが、ステップ数は変更されません。