[問題案] Palindromes in Deque

[NachiaVivias]

[問題案] Palindromes in Deque

target : Double-Ended Palindromic Trees

Problem

初期状態の文字列が与えられて、以下の 4 つの操作を処理せよ。

• $(0,c)$ : push back $c$ → suffix の回文の長さの最大を出力
• $(1,c)$ : push front $c$ → prefix の回文の長さの最大を出力
• $(2)$ : pop back → suffix の回文の長さの最大を出力
• $(3)$ : pop front → prefix の回文の長さの最大を出力

Constraint

• 英小文字

Solution / Reference

• Double-Ended Palindromic Trees
• #134 : 文字列の変更がない場合はこれ

[maspypy]

良さそうです。

回文の種類数とかも聞いてもいいかもしれません。 例：クエリのたびに、3つ組（種類数, longest prefix, longest suffix）を出力。

[hos-lyric]

参考：queue https://codeforces.com/contest/1738/problem/H

[maspypy]

クエリのたびに、3つ組（種類数, longest prefix, longest suffix）を出力

これでお願いします。（種類数は聞かないと、不要なノードの削除処理を問えないという意図があります）