最小の文字を挿入して文字列を返信します

背景

          ，      ，      ，       。        ，          。

タイトルの説明
1つの文字列Sが与えられると、文字列の任意の位置に文字を挿入することによって、文字列を逆文字列にすることができる.最小挿入文字数を求めます.
例:
ab -> bab  1
aa -> aa    0
abca -> acbca 1
テーマの出所:マイクロ信号は字の娘の中に待ちます
問題を解く構想.
元の列Sの中で最も長い子の列Lを見つけることができて、この子の列は回文で、それでは私達はどれだけの文字のはいの元の列を挿入して回文になることを知ることができます.
ans = strlen(s) - strlen(L)
問題は文字列の最長回文サブシーケンスを求めることに変わり、この問題は最長共通サブシーケンスの解法を使用することができ、解法は以下の通りである.
1.Sの逆順列S′を求める.
2.では、SとS'の最も長い共通サブシーケンスL、LはSの最も長い回文サブシーケンスである(この法則は推論で発見された).
3.では、問題は以下の通りです.
ans = strlen(s) - strlen(L).
例えば、S=abcaならS'=acba、L=abaなら答えは1.すなわちa’c‘bcaである.ここで、「c」は挿入された文字です.
アルゴリズム解析
このアルゴリズムの核心は最長の共通サブシーケンスを求めることであり、
最長共通サブシーケンスにはDPの求め方があり,アルゴリズムの複雑さは時間も空間もOである(n^2)
解法二
原作者提供
主にダイナミックプランニングを採用し、ダイナミックプランニングは主に両端文字から比較するため、サブ問題が繰り返される.
問題を式S(0,n−1)として表すとすると,
                           if(a[0] = a[n-1])                                 s(0,n-1) == s(2,n-2)                             else                                s(0,n-1) == min( s(1,n-2) , s(2,n-1) ) + 1
ここで、a[i]は、シリアルSのi番目の文字である.