H問題秋祭 | 工学部

H問題 - Gomamayo (hard)

`N`個の文字列`S_i,\quad(1\leq i\leq N)`が与えられます。あなたは`S_i`のうちいくつかを次の条件を満たすように連結せさ、新しい文字列`T`を作りたいです。

[条件]

文字列`A`と文字列`B`は、`A`の末尾と`B`の先頭の文字が完全に一致するならば文字列`A`と文字列`B`を使用して`A B`の順で連結することができる。
すなわち、`AB`は`A`と`B`の境界を等しくする狭義ゴママヨ文字列(C問題参照)となる。
`S_i`は1回のみ使用することができる。

考えられる新しい文字列`T`のうち最長となるものの長さを求めてください。

`N`
`S_1 \quad S_2 \quad \cdots \quad S_N`

考えられる最長の新しい文字列`T`の長さを1行で出力せよ。

6
abc bba cbb ace bad cge

6
a a a b b b

１文字の先頭と末尾は等しいので、aaaやbbbと連結することができます。それぞれの文字列は１回以下使用できることに注意してください。
aaaと連結してもbbbと連結しても長さは3で、最長です。

1
a

提出はここから