SRM607Div1Easy
問題
長さNの文字列が与えられる。文字の要素は小文字のアルファベットか?である。?はランダムに小文字のアルファベットになる。回文となる部分文字列の個数の期待値を求めよ。
解法
?に対して全探索をすると、となる。ある部分文字列が回文になるためには、その両端を取り除いた部分文字列が回文である必要がある。回分の中心となる点を定め、そこから回文を構築できるかを探索していく。
計算量
回文構築:O(N)
中心点探索:O(N)
全体:
長さNの文字列が与えられる。文字の要素は小文字のアルファベットか?である。?はランダムに小文字のアルファベットになる。回文となる部分文字列の個数の期待値を求めよ。
?に対して全探索をすると、となる。ある部分文字列が回文になるためには、その両端を取り除いた部分文字列が回文である必要がある。回分の中心となる点を定め、そこから回文を構築できるかを探索していく。
回文構築:O(N)
中心点探索:O(N)
全体: