题目名称 1709. [SPOJ 705] 不同的子串
输入输出 subst1.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 Gravatarcstdio 于2014-09-23加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:163, 提交:309, 通过率:52.75%
GravatarAAAAAAAAAA 100 0.000 s 0.00 MiB C++
GravatarHzoi_Mafia 100 0.000 s 0.00 MiB C++
GravatarJobs.T 100 0.000 s 0.16 MiB C++
Gravatarztx 100 0.000 s 1.87 MiB C++
GravatarMarvolo 100 0.001 s 33.79 MiB C++
GravatarGo灬Fire 100 0.002 s 2.55 MiB C++
GravatarAntiLeaf 100 0.008 s 11.02 MiB C++
Gravatarsxysxy 100 0.014 s 10.97 MiB C++
Gravatar半汪 100 0.017 s 12.62 MiB C++
GravatarBFZD 100 0.018 s 0.90 MiB C++
关于 不同的子串 的近10条评论(全部评论)
自己乱搞总算出来了
GravatarHale
2019-07-30 16:08 10楼
1A首道后缀数组
GravatarShirry
2017-12-22 13:27 9楼
$SA$基本结论题= =
GravatarHzoi_Mafia
2017-09-28 20:34 8楼
可持久化后缀自动机初试。
Gravatarsxysxy
2017-04-22 08:33 7楼
后缀自动机 : 秒了
Gravatarsxysxy
2016-08-15 18:46 6楼
不要保存很多份代码= =,你也不知道自己最后改对的是哪一个....
GravatarFmuckss
2016-06-15 10:01 5楼
后缀自动机首题留念
Gravatar/k
2016-01-15 20:48 4楼
回复 @mikumikumi :
strlen不是O(n)大暴力扫……吗……
Gravatarcstdio
2015-12-13 11:31 3楼
strlen这个函数相当耗时,尽量减少调用。
Gravatarmikumikumi
2015-12-12 21:17 2楼
第一道后缀数组题。。
话说不会写nlogn就写nlog^2n好了。。
还有计算height的时候算了好久TAT。。各种策不清rank,height,rank[i-1],rank[i]-1,height[i]-1和height[i-1]
果然没救了(╯‵□′)╯︵┻━┻
GravatarHouJikan
2015-03-30 21:10 1楼

1709. [SPOJ 705] 不同的子串

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

【题目描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

ABABA

【样例输出】

9

【来源】

SPOJ 705 New Distinct Substrings