分数: 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