33OJ
登录 注册

#P17835. 你是一只猫娘

    ID: 20511 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>字符串上海O2优化枚举2026高校校赛

你是一只猫娘

题目描述

你是一只能预测未来的猫娘,已经知晓了未来自己将要说出的某一语句。

此语句是一个仅包含小写英文字母的字符串 SS。

但是未来并非不能改变,对于每一种小写英文字母,你可以将其改写为另一种小写英文字母(改写后可以保持不变),但需保证不同的小写英文字母改写后不同。

形式化地,你可以任选一种小写英文字母集合到自身一一对应的映射

F:{a,b,…,z}→{a,b,…,z}F:\{a,b,\ldots,z\}\rightarrow\{a,b,\ldots,z\}

然后将 S=s1s2…sn‾S=\overline{s_1s_2\ldots s_n} 改写为 T=F(s1)F(s2)…F(sn)‾T=\overline{F(s_1)F(s_2)\ldots F(s_n)}。

作为一只合格的猫娘,你希望改写后的语句 TT 具有的 nya\texttt{nya} 子串1^{1}数量最多。

请你求出,nya\texttt{nya} 子串出现数量最多是多少。

1^{1} 对于一个字符串 SS,若可以从 SS 中选取一段连续的字符得到字符串 TT,则称 TT 是 SS 的一个子串。一个子串可能在字符串中出现多次,我们按照其在原字符串中的起始位置统计出现次数;即使不同的出现位置有所重叠,也会分别计数。

输入格式

第一行一个整数 nn(1≤n≤2×1051 \leq n \leq 2 \times 10^5),表示字符串 SS 的长度。

第二行一个字符串 SS,保证只包含小写英文字母。

输出格式

一行一个整数,表示改写后的语句最多能出现多少 nya\texttt{nya} 子串。

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}$$

这样字符串 abcdabc\texttt{abcdabc} 被改写为了 nyadnya\texttt{nyadnya},nya\texttt{nya} 子串出现了 22 次,可以证明这是最大值。