きままにものづくり

日々の気付いたことなんかを書いてます。

SRM607Div1Easy

問題

長さNの文字列が与えられる。文字の要素は小文字のアルファベットか?である。?はランダムに小文字のアルファベットになる。回文となる部分文字列の個数の期待値を求めよ。

解法

?に対して全探索をすると、 O(26^N)となる。ある部分文字列が回文になるためには、その両端を取り除いた部分文字列が回文である必要がある。回分の中心となる点を定め、そこから回文を構築できるかを探索していく。

計算量

回文構築:O(N)
中心点探索:O(N)
全体: O(N^2)

コード

広告を非表示にする