Substring Not Subsequence
题号:NC276695
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

给定长度为 n 的字符串 S,请求出有多少个非空字符串 T 满足:

  •  作为子串在  中出现至少一次;
  • S 中不存在不连续的子序列等于 T

输入描述:

第一行,一个正整数 

第二行,一个长为  的字符串 

输出描述:

一行,一个正整数,表示答案。
示例1

输入

复制
5
abcaa

输出

复制
9

说明

共有 9 个  满足条件:\texttt{a},\texttt{ab},\texttt{abc},\texttt{abcaa},\texttt{b},\texttt{bc},\texttt{bcaa},\texttt{c},\texttt{caa}

串 \texttt{abca} 不满足条件,因为取下标 1,2,3,5 可以形成 \texttt{abca},但是这些下标不连续。

串 \texttt{aba} 也不满足条件,因为 \texttt{aba} 没有作为子串出现过。

备注:

  •  中只含小写英文字母。