#P2559. [Poi1998] AB-words Abs

    ID: 1620 传统题 1000ms 256MiB 尝试: 4 已通过: 1 难度: 5 上传者: 标签>字符串树算法树哈希字符串哈希最小表示法CF1700递归排序

[Poi1998] AB-words Abs

Description

每一个由字母 a 和 b 组成的序列(或是空序列),称为 ab-word。

如果 X = [x1, …, xn] 是一个 ab-word,并且有整数 i, j(1 <= i <= j <= n),那么 X[i..j] 表示由字母 xi, …, xj 组成的 X 的子串。

如果一个 ab-word X = [x1, …, xn] 满足:

  • 字母 a 的个数等于字母 b 的个数;
  • 对任意 i = 1, …, n,在前缀 X[1..i] 中,字母 a 的个数不少于字母 b 的个数;

则称该 ab-word X 为 好的(good)。

下面给出两个好的 ab-words 之间“相似”的递归定义:

  • 任意两个空 ab-word(字符串内无字母)是相似的。

  • 两个非空的好 ab-words X = [x1, …, xn] 和 Y = [y1, …, ym] 是相似的,当且仅当 n = m 且满足以下条件之一:

    1. x1 = y1,xn = yn,并且 X[2..n-1] 与 Y[2..n-1] 相似,且它们都是好的 ab-words。

    2. 存在 i(1 <= i <= n),使得 X[1..i] 和 X[i+1..n] 都是好的 ab-words,并且满足下列之一:

      a. Y[1..i]、Y[i+1..n] 也是好的 ab-words,且
      X[1..i] 与 Y[1..i] 相似,X[i+1..n] 与 Y[i+1..n] 相似;

      b. Y[1..n-i]、Y[n-i+1..n] 是好的 ab-words,且
      X[1..i] 与 Y[n-i+1..n] 相似,X[i+1..n] 与 Y[1..n-i] 相似。

一个好的 ab-words 的非空集合 S 的 多样性的水平(diversity level) 定义为:
在 S 中最多能选出的 ab-words 的个数,使得选出的任意一对 w1、w2 都满足 w1 不相似于 w2。


Input Format

写出以下一个程序:

  • 读入集合 S;
  • 计算集合 S 的多样性的水平。

输入文件第一行是集合 S 的元素个数 n(1 <= n <= 1000)。
接下来 n 行,每行一个 ab-word(仅由 a、b 组成)。每个 ab-word 的首字母是该行的首字符,两个连续字母之间没有空格。
每个 ab-word 的长度是 [1..200] 范围内的整数。


Sample

Input

3
aabaabbbab
abababaabb
abaaabbabb

Output

2