#P5536. String

    ID: 4539 传统题 3000ms 256MiB 尝试: 8 已通过: 4 难度: 9 上传者: 标签>CF2600省选/NOI-后缀自动机endpos 等价类按长度传播出现次数DAG 动态规划计数排序

String

题目描述

给定一个长度为 nn、仅包含小写英文字母的字符串 SS。

你有一个字符串 TT,初始为空串。接下来恰好进行 nn 次操作,每次可以在 TT 的开头或末尾添加一个任意小写英文字母。

设第 ii 次操作结束后,TT 在 SS 中作为连续子串出现的次数为 fif_i(允许不同出现位置之间重叠)。

请最大化

ans=∑i=1nfi.\mathrm{ans}=\sum_{i=1}^{n} f_i.

输入格式

第一行一个正整数 nn,表示字符串 SS 的长度。

第二行一个长度为 nn、仅包含小写英文字母的字符串 SS。

输出格式

输出一个整数,表示 ans\mathrm{ans} 的最大值。

输入输出样例 #1

输入

6
abcabc

输出

9

样例解释

一种可行方案是每次在末尾添加字符,依次形成:

a、ab、abc、abca、abcab、abcabc。

其出现次数依次为 2,2,2,1,1,12,2,2,1,1,1,总和为 99。

数据范围

1≤n≤2×1051\le n\le 2\times 10^5。