#P4024. 神犇的字符串集合

    ID: 3225 传统题 2000ms 512MiB 尝试: 72 已通过: 17 难度: 9 上传者: 标签>难度分类省选/NOI-图论状态扩展图动态规划记忆化搜索DAG 动态规划枚举与搜索深度优先搜索字符串后缀数组Kasai 算法LCP+RMQ数据结构ST 表CF2600By佚名上传

神犇的字符串集合

题目描述

初始时神犇有一个含 nn 个字符串的字符串集合。这里的集合是可以有重复元素的。每次神犇可以进行以下两个操作:

  1. 向集合中加入一个已经存在于集合中的字符串;
  2. 将集合中的两个字符串删除,将两个字符串前后拼接起来形成的字符串加入集合中。

因为神犇是神犇,所以他想出了这样一个问题:可以执行任意有限次操作。在所有可得到的字符串中,求回文子串长度的最大值。如果长度没有上界,则输出无界的标记。这么简单的问题神犇当然会做了,于是他想考考你。

输入格式

输入数据的第一行是一个整数 nn。以下 nn 行,每行一个字符串。

输出格式

输出一行。如果回文子串的长度没有上界,输出 Infinity,否则输出最长长度。

样例 #1

样例输入 #1

2
abc
cde

样例输出 #1

2

数据范围

对于 100%100\% 的数据,N≤100N\le 100,保证所有字符串的长度之和≤105\le 10^5,所有字符串只包含小写英文字母。最终答案在 pascal 的 longint,C/C++ 的 int 范围之内。