(ユーザー解説です)

公式解説に計算量の記載がないので簡単に付記します。以下では文字列 \(S\) の長さを \(N\) とします。

この問題は次の \(3\) つのパートからなります。

• すべての回文を列挙して、重複を取り除く。
• 列挙した回文からなるすべての回文の組について、一方が他方の部分列になっているか判定する。
• 得られたグラフの独立集合を最大マッチングに帰着させて、最大流を流す。

1, 2 番目のパートはコンテストでは見慣れないアルゴリズムを利用すれば高速に解くことができますが (Palidromic tree) 、ここではライブラリを使用しない愚直な実装の計算量を考えてみましょう。

1 番目のパートはラフな実装で \(\mathrm{O}(N^3 \log N)\) で計算できるのが確認できると思います。(関連 : ABC226-B )

2 番目のパートはおそらく計算量が少し非自明だと思います。
長さ \(n\) の文字列が長さ \(m\) \((n \leq m)\) の文字列の部分列であるか判定するには最大で \(m-n+1\) 回の文字列一致判定が必要なので、文字列の種類数が \(\mathrm{O}(N)\) 個、文字列の長さが \(\mathrm{O}(N)\) なのも加味すると \(\mathrm{O}(N^4)\) かかることがわかり、少し TL が不安になる方もいるのではないでしょうか。
そこで、「文字を比較する回数が何回発生するか」の上界を定数倍も含めて数えてみましょう。\(N\) 個の回文の長さを昇順に並べた列は最大でも \(1,2, \dots, N\) という列になるのを利用すると、文字同士の比較回数は最大でも

\[\sum_{1 \leq a \lt b \leq N} (b - a + 1) a = \frac{N^4}{24} + \mathrm{O}(N^3)\]

回しか発生しないとわかるので、文字の比較回数は \(\frac{200^4}{24} \simeq 6.67 \times 10^7\) 回を上界として抑えられるとわかります。よって、 2 番目のパートは定数倍の軽い \(\mathrm{O}(N^4)\) で解くことができました。

• なお、実際に \(\frac{N^4}{24} + \mathrm{O}(N^3)\) 回の比較が発生するケースは発生せず、実際の定数倍はさらに軽くなります。
  
  • 長さの列が \(1,2, \dots, N\) であるとき、回文の列は a,aa,aaa, … となるので、一方が他方の部分列であるかは \(1\) 回の文字列比較で出来るので \(\mathrm{O}(N^3)\) になります。
• 厳密な比較回数の評価はよくわかっていませんが、計算量としては \(\Theta (N^4)\) なのは確認できて、たとえば 「a を \(66\) 文字, b を \(1\) 文字, a を \(66\) 文字, c を \(1\) 文字, a を \(66\) 文字 をこの順に繋げた文字列」は \(\mathrm{O}(N^4)\) 回 (たぶん \(\frac{N^4}{216} + \mathrm{O}(N^3)\) 回？) の文字の比較が発生します。これより比較回数の多いケースがあるかはよくわかっていません。

3 番目のパートは以下のいずれかの方法により \(\mathrm{O}(N^{\frac{8}{3}})\) を達成できます。

• ACL の Max Flow を利用する。構成するグラフは頂点数 \(\mathrm{O}(N)\), 辺数 \(\mathrm{O}(N^2)\) で辺の容量がすべて \(1\) のグラフなので、ACL のリファレンス を参考にすると計算量は \(\mathrm{O}(N^{\frac{8}{3}})\) になる。
• Hofcroft-Karp algorithm を利用する。計算量は \(\mathrm{O}(N^{2.5})\) になる。

以上より、この問題の計算量は定数倍が非常に軽い \(\mathrm{O}(N^4)\) であり、ACL を使えばシンプルな実装で十分 TL に間に合うことが確認できました。