华师一附中OI组

标题: P2408 不同子串个数 [打印本页]

作者: admin 时间: 2018-6-29 17:59
标题: P2408 不同子串个数

https://www.luogu.org/problemnew/show/P2408

题目背景
因为NOI被虐傻了，蒟蒻的YJQ准备来学习一下字符串，于是它碰到了这样一道题：
题目描述
给你一个长为N的字符串，求不同的子串的个数
我们定义两个子串不同，当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。
子串的定义：原字符串中连续的一段字符组成的字符串
输入输出格式
输入格式：
第一行一个整数N

接下来一行N个字符表示给出的字符串

输出格式：
一行一个整数，表示不一样的子串个数

输入输出样例
输入样例#1：
5
aabaa
输出样例#1：
11
输入样例#2：
3
aba
输出样例#2：
5
说明
请使用64位整数来进行输出

（具体来说，C++和C选手请使用long long 类型，pascal选手请使用Int64）

由于输入文件过大，请使用高效的读入方法（具体的，c++和c选手请不要使用cin，pascal选手不需要管）

对于30%的数据， N≤1000

对于100%的数据， N≤10^5

欢迎光临华师一附中OI组 (http://hsyit.cn/)