#P17835. 你是一只猫娘
你是一只猫娘
题目描述
你是一只能预测未来的猫娘,已经知晓了未来自己将要说出的某一语句。
此语句是一个仅包含小写英文字母的字符串 。
但是未来并非不能改变,对于每一种小写英文字母,你可以将其改写为另一种小写英文字母(改写后可以保持不变),但需保证不同的小写英文字母改写后不同。
形式化地,你可以任选一种小写英文字母集合到自身一一对应的映射
然后将 改写为 。
作为一只合格的猫娘,你希望改写后的语句 具有的 子串数量最多。
请你求出, 子串出现数量最多是多少。
对于一个字符串 ,若可以从 中选取一段连续的字符得到字符串 ,则称 是 的一个子串。一个子串可能在字符串中出现多次,我们按照其在原字符串中的起始位置统计出现次数;即使不同的出现位置有所重叠,也会分别计数。
输入格式
第一行一个整数 (),表示字符串 的长度。
第二行一个字符串 ,保证只包含小写英文字母。
输出格式
一行一个整数,表示改写后的语句最多能出现多少 子串。
7
abcdabc
2
提示
对于样例,可以选择如下映射:
$$\begin{array}{c|cccccccccccccccccccccccccc} x &a&b&c&d&e&f&g&h&i&j&k&l&m&n&o&p&q&r&s&t&u&v&w&x&y&z\\ \hline F(x) &n&y&a&d&e&f&g&h&i&j&k&l&m&b&o&p&q&r&s&t&u&v&w&x&c&z \end{array}$$这样字符串 被改写为了 , 子串出现了 次,可以证明这是最大值。