NAPC 2025 OPEN 2026/03/27 09:00 ~ 2026/03/27 14:15 5:15:00.000

I Three Palindromes

問題
制限時間: 6 sec メモリ制限: 2048 MB
problem
問題文

英小文字からなる文字列 $S$ が与えられます。

$S$ を非空な $3$ つの文字列に分割することを考えます。 分割された $3$ つの文字列がすべて回文になるような分割方法が存在するかどうかを判定してください。

より厳密には、以下をすべて満たすような整数 $i,j$ が存在するかどうかを判定してください。ただし、$S_i$ は $S$ の $i$ 文字目を表し、 $|S|$ は $S$ の長さを表します。

  • $1 < i < j \leq |S|$
  • $S_1,S_2,\ldots, S_{i-1}$ をこの順につなげた文字列は回文である。
  • $S_i,S_{i+1},\ldots,S_{j-1}$ をこの順につなげた文字列は回文である。
  • $S_j,S_{j+1},\ldots,S_{|S|}$ をこの順につなげた文字列は回文である。

存在する場合は Yes、存在しない場合は No を出力してください。

制約
  • $S$ は英小文字のみからなる文字列
  • $3 \leq |S| \leq 10^5$
入力

入力は以下の形式で標準入力から与えられます。

$S$
出力

存在する場合は Yes、存在しない場合は No を出力してください。

入力例 1
abacabaxxa
出力例 1
Yes

abacaba, xx, a と分割できます。

入力例 2
naist
出力例 2
No