luogu#P9543. [湖北省选模拟 2023] 日记 / diary

[湖北省选模拟 2023] 日记 / diary

题目描述

小 M 决定开始写日记,但她不愿意花费太多时间构思日记的内容。为此,她找来了一个长度为 nn 的字符串 SS,决定任取 SS 的一个前缀 PP,再任取 SS 的一个后缀 QQ,将 PPQQ 顺次连接起来得到的字符串 P+QP+Q 作为日记的内容。这里,空串也认为是 SS 的前缀和后缀,因此 PPQQ 各有 n+1n+1 种取法。

当然了,这样形成的很多字符串是无意义的。具体而言,小 M 认为一个已知的长度为 mm 的字符串 TT 为重要信息,所有包含该重要信息作为子串的字符串都是有意义的,反之则是无意义的。

请你求出,小 M 一共能写出多少种本质不同的有意义的字符串。本质不同就是说,对于某个有意义的字符串 AA ,即使它可以被若干种取前缀和后缀的方式得到,也只应被计入一次。

输入格式

输入共两行。

第一行一个字符串 SS

第二行一个字符串 TT

输出格式

一行一个整数,所求答案。

aab
ab
7
mikageandspica
spica
140
见选手目录下的 diary/diary3.in 与 diary/diary3.ans。
见选手目录下的 diary/diary3.in 与 diary/diary3.ans。
见选手目录下的 diary/diary4.in 与 diary/diary4.ans。
见选手目录下的 diary/diary4.in 与 diary/diary4.ans。
见选手目录下的 diary/diary5.in 与 diary/diary5.ans。
见选手目录下的 diary/diary5.in 与 diary/diary5.ans。

提示

样例 1 解释

对于第一组样例,所有能够形成的有意义字符串分别为 abaabaaabaaaabaabaabaababaabb,一共 77 种。

子任务

对于所有测试数据,保证 1S5×1061 \leq |S| \leq 5 \times 10^61T2S1 \leq |T| \leq 2|S|,输入的字符串 SSTT 仅包含小写英文字母。其中 S,T|S|,|T| 分别表示串 SSTT 的长度。

  • 2023.8.21 添加一组 hack 数据。