407817: GYM102897 D Palindrome Hard Problem

最近 wifePie 学长在研究字符串难题，对回文问题颇有研究，经常一言不合就掏出回文树和马拉车，并且基于深度研究的基础上提出以下问题：

给出 $$$n$$$ 个长度相同的，只包含小写字母的字符串，标号为 $$$1$$$ 到 $$$n$$$。并且我们约定第 $$$i$$$ 个字符串为 $$$s_i$$$。你可以进行不限次数的如下操作，每个操作都会使得字符串个数减 $$$1$$$：

• 把 $$$s_i$$$ 拼接到 $$$s_j$$$ 的后面, 操作后 $$$s_i$$$ 消失。
• 把 $$$s_i$$$ 拼接到 $$$s_j$$$ 的前面, 操作后 $$$s_i$$$ 消失。
• 将 $$$s_i$$$ 和 $$$s_j$$$ 进行交错排列, 形成一个新的字符串 $$$S$$$。操作后 $$$S$$$ 替代 $$$s_j$$$ 的位置，然后 $$$s_i$$$ 和 $$$s_j$$$ 消失。(例如 "aaaa" 与 "bbbb" 重构后 得到的串为 "abababab")。
• 直接舍弃 $$$s_i$$$。

经过若干次上述操作后，你可以获得一个终极串，问这个终极串最多能分割成多少个回文串。

值得注意的是，上述操作是由你选择如何操作的，你要保证你最终得到的终极串能够分割出的回文串的数量是最多的。

单组数据评测。

第一行包含一个正整数 $$$n(1 \leq n \leq 10^5)$$$。

接下来的 $$$n$$$ 行，每行有一个长度为 $$$m$$$ 的字符串, 其中只包含小写字母。

数据保证 $$$n \cdot m \leq 10^6$$$。

输出包含一个正整数，表示终极串中最多能分割出的回文串的数量。

1
a

1

2
a
b

2