← 返回题目列表

AtCoder · abc452_d

D. 无子序列

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你字符串 S 和 T 由小写英文字母组成。

非空子串之中 s of S,计算那些这样做的 不 包含 T 作为(不一定是连续的)子序列。

这里,两个子串 S 如果从不同的位置获取,即使它们作为字符串相等,也会被区分。

什么是子串? 字符串的子字符串 X 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 X.
什么是子序列? 字符串的子序列 X 是删除零个或多个元素得到的字符串 X 并按原始顺序排列剩余元素。

约束

  • S 是由小写英文字母组成的字符串。
  • 1\le |S|\le2\times10 ^ 5,其中 |S| 是长度 S.
  • T 是由小写英文字母组成的字符串。
  • 1\le |T|\le50,其中 |T| 是长度 T.

输入

输入由标准输入按以下格式给出:

S
T

输出

输出答案。


示例输入 1

abrakadabra
aba

示例输出 1

51

例如,子字符串 abr 由第一个到第三个字符组成 S 不包含 T 作为子序列。 包括这个在内,还有 51 满足条件的子串,例如 k (仅第五个字符 S)和 akada (第四到第八个字符 S).

请注意,该字符串 abr 可以作为第一个到第三个字符的子字符串获得 S 并作为从第八个到第十个字符的子字符串 S,但是它们是从不同的位置取出的,所以是分开统计的。


示例输入 2

aaaaa
a

示例输出 2

0

的所有非空子字符串 S 包含 T 作为子序列。

因此,不存在满足条件的子串,因此输出 0.


示例输入 3

rdddrdtdcdrrdcredctdordoeecrotet
dcre

示例输出 3

263