palindromic substrings

2 secs 1024 MB
naskya's icon naskya

※ 大きい画面での閲覧を推奨します。

問題の説明

文字列 SS の空文字列を除く連続部分文字列のうち、回文(前から読んでも後ろから読んでも等しい文字列)である文字列の個数を数えてください。ただし、複数の部分文字列が文字列として一致する場合もその部分文字列を取り出してきた場所が違う場合には区別します。(問題文はこれをより厳密に表現しています。)

SSabcba\mathtt{abcba} のとき、abcbaabcbaabcbaabcbaabcbaabcbaabcba\mathtt{\textcolor{red}{a}bcba \hspace{.5em} a\textcolor{red}{b}cba \hspace{.5em} ab\textcolor{red}{c}ba \hspace{.5em} abc\textcolor{red}{b}a \hspace{.5em} abcb\textcolor{red}{a} \hspace{.5em} a\textcolor{red}{bcb}a \hspace{.5em} \textcolor{red}{abcba}} の 7 個の連続部分文字列が回文となります。

SSaaaaa\mathtt{aaaaa} のとき、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\mathtt{\textcolor{red}{a}aaaa \hspace{.5em} a\textcolor{red}{a}aaa \hspace{.5em} aa\textcolor{red}{a}aa \hspace{.5em} aaa\textcolor{red}{a}a \hspace{.5em} aaaa\textcolor{red}{a} \hspace{.5em} \textcolor{red}{aa}aaa \hspace{.5em} a\textcolor{red}{aa}aa \hspace{.5em} aa\textcolor{red}{aa}a \hspace{.5em} aaa\textcolor{red}{aa} \hspace{.5em} \textcolor{red}{aaa}aa \hspace{.5em} a\textcolor{red}{aaa}a \hspace{.5em} aa\textcolor{red}{aaa} \hspace{.5em} \textcolor{red}{aaaa}a \hspace{.5em} a\textcolor{red}{aaaa} \hspace{.5em} \textcolor{red}{aaaaa}} の 15 個の連続部分文字列が回文となります。


解説

回文である連続部分文字列のことを回文連続部分文字列ということにします。

Manacher's algorithm を用いると、文字列の各位置を中心とする最長の回文連続部分文字列の長さを線形時間で列挙することができます。

具体的には、文字列 abbba\mathtt{abbba} に対して

というような配列を時間計算量 O(N)O(N) で作成することができます。ここで、NN は文字列の長さを表します。


長さ 5 の回文には同じ位置を中心とする長さ 3, 1 の回文が含まれます (例えば abcba\mathtt{abcba} には bcb\mathtt{bcb}c\mathtt{c} が含まれる)。

長さ 6 の回文には同じ位置を中心とする長さ 4, 2 の回文が含まれます (例えば abccba\mathtt{abccba} には bccb\mathtt{bccb}cc\mathtt{cc} が含まれる)。

同様に、文字列のある位置を中心とする最長の回文連続部分文字列の長さが nn であるとき、その位置を中心とする回文連続部分文字列の個数は n2\left\lceil\frac{n}{2}\right\rceil (回文の「半径」と呼ばれる値)となります。よって、Manacher's algorithm を用いて最長の回文連続部分文字列の長さを格納した配列を求めた後に各要素を 2 で割って切り上げた値の総和を求めることによって時間計算量 O(N)O(N) でこの問題を解くことができます。(元から回文の半径を求める実装をしている場合は配列の要素の総和を取るだけでよいです。)


解答例(Python 3)

解答例(C++)


この問題は完全に知識問題(Manacher's algorithm を知っていれば解けるし知らなければ解けない)だと思って出題したのですが、皆さんの解答を見ると他の方法でも解かれているようです。興味のある方は他の解法も考えてみてください。