#P3654. 图森

图森

[湖南集训] 图森

题目描述

给定一个允许重复元素的字符串集合 SS,初始含有 nn 个字符串。你可以进行以下任意次操作。

  • 在 SS 中再加入一份已经存在的字符串。
  • 从 SS 中选取两个字符串,将它们按所选顺序拼接,把得到的字符串加入 SS。

求通过这些操作能得到的最长回文子串的长度。回文子串必须连续,可以跨越拼接位置。如果回文子串的长度没有上界,输出 Infinity。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行一个由小写英文字母组成的非空字符串。

输出格式

若最长长度有限,输出这个长度。否则输出 Infinity。

3
abc
abacde
ecab
7
1
ha
Infinity

样例解释

第一个样例可以把 ecab 与 abacde 拼接成 ecababacde,其中回文子串 cababac 长为 77。

第二个样例重复拼接 ha,可得到任意长的奇数长度回文子串,如 h、hah、hahah。

数据范围

下表的 LL 指单个字符串的长度。

测试点 字符串个数 长度上界
1–2 n=1n=1 L≤100L\le100
3–6 L≤100000L\le100000
7–12 n≤50n\le50 L≤100L\le100
13–20 n≤100n\le100 L≤1000L\le1000