题目名称	1709. [SPOJ 705] 不同的子串
输入输出	`subst1.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cstdio 于2014-09-23加入
开放分组	全部用户
提交状态
分类标签	后缀数组字符串模式匹配后缀自动机后缀树 SPOJ
	分享题解

通过：165，提交：313，通过率：52.72%
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
Hzoi_Mafia	100	0.000 s	0.00 MiB	C++
Jobs.T	100	0.000 s	0.16 MiB	C++
ztx	100	0.000 s	1.87 MiB	C++
Marvolo	100	0.001 s	33.79 MiB	C++
Go灬Fire	100	0.002 s	2.55 MiB	C++
AntiLeaf	100	0.008 s	11.02 MiB	C++
sxysxy	100	0.014 s	10.97 MiB	C++
半汪	100	0.017 s	12.62 MiB	C++
BFZD	100	0.018 s	0.90 MiB	C++

关于不同的子串的近10条评论(全部评论)
逆天大写 ┭┮﹏┭┮ 2025-01-05 10:54 11楼
自己乱搞总算出来了 Hale 2019-07-30 16:08 10楼
1A首道后缀数组 Shirry 2017-12-22 13:27 9楼
$SA$基本结论题= = Hzoi_Mafia 2017-09-28 20:34 8楼
可持久化后缀自动机初试。 sxysxy 2017-04-22 08:33 7楼
后缀自动机 : 秒了 sxysxy 2016-08-15 18:46 6楼
不要保存很多份代码= =，你也不知道自己最后改对的是哪一个.... Fmuckss 2016-06-15 10:01 5楼
后缀自动机首题留念。 /k 2016-01-15 20:48 4楼
回复 @mikumikumi : strlen不是O(n)大暴力扫……吗…… cstdio 2015-12-13 11:31 3楼
strlen这个函数相当耗时，尽量减少调用。 mikumikumi 2015-12-12 21:17 2楼

1709. [SPOJ 705] 不同的子串

★★★ 输入文件：subst1.in 输出文件：subst1.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

给定一个字符串，计算其不同的子串个数。

【输入格式】

一行一个仅包含大写字母的字符串，长度<=50000

【输出格式】

一行一个正整数，即不同的子串个数。

【样例输入】

ABABA

【样例输出】

9

【来源】

SPOJ 705 New Distinct Substrings