#O1101. 不同子串个数

不同子串个数

题目描述

给定一个只含小写字母的字符串 ss,求它有多少个本质不同的非空子串。

输入格式

一行一个字符串 ss。

输出格式

一行一个整数,表示不同子串个数。

样例 #1

样例输入 #1

abab

样例输出 #1

7

数据规模与约定

数据范围 说明
$1 \le s
  • 每个状态 vv 表示 len(v)−len(link(v))\text{len}(v)-\text{len}(\text{link}(v)) 个不同的子串,全部求和即可。