#P18735. [正睿NOI2021训练] 数据结构
[正睿NOI2021训练] 数据结构
数据结构
给定一个仅包含小写英文字母的字符串 。
对于两个非空字符串 ,称 “跟随”,当且仅当:
- 是 的一个子串。
- 对 在 中的每一次出现,若该次出现之后至少还剩 个字符,则紧接着的 个字符必须组成 ;若剩余字符不足 ,则这次出现不施加要求。
求满足上述条件的有序字符串对 的数量,其中 都必须是 的非空子串。按字符串内容区分,不按出现位置区分。不同位置的出现可以相互重叠。
输入格式
第一行一个正整数 ;第二行一个长度为 的字符串 。
输出格式
输出一个整数,表示符合要求的有序字符串对数量。
数据范围
, 仅含小写英文字母。
样例 1
输入
4
aabc
输出
6
样例 2
输入
7
abacaba
输出
44