AT_abc452_d.[ABC452D] No-Subsequence Substring
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定由小写英文字母组成的字符串 S 和 T。
求 S 的所有非空子串中,不包含 T 作为(不一定连续的)子序列的子串个数。
这里,S 的两个子串只要取出的位置不同,即使字符串内容相同也视为不同子串。
子串:字符串 X 的子串是指从 X 开头删除 0 个以上字符、从末尾删除 0 个以上字符后得到的字符串。
子序列:字符串 X 的子序列是指从 X 中删除 0 个以上元素后,剩余元素按原顺序排列得到的字符串。
输入格式
输入从标准输入以以下格式给出:
S T
输出格式
一行,输出答案。
输入输出样例
输入#1
abrakadabra aba
输出#1
51
输入#2
aaaaa a
输出#2
0
输入#3
rdddrdtdcdrrdcredctdordoeecrotet dcre
输出#3
263
说明/提示
样例解释 1
例如,S 的第 1 个字符到第 3 个字符组成的子串 abr 不包含 T 作为子序列。此外,k(仅 S 的第 5 个字符)和 akada(S 的第 4 个字符到第 8 个字符)等共 51 个子串满足条件。
注意:abr 既可以作为 S 的第 1 到 3 个字符的子串,也可以作为第 8 到 10 个字符的子串,但由于取出位置不同,它们被视为不同的子串进行计数。
样例解释 2
S 的所有非空子串都包含 T 作为子序列。因此没有满足条件的子串,输出 0。
数据范围
-
S 由小写英文字母组成
-
记 ∣S∣ 为 S 的长度,满足 1≤∣S∣≤2×105
-
T 由小写英文字母组成
-
记 ∣T∣ 为 T 的长度,满足 1≤∣T∣≤50
输入解题思路,AI测评打分。不知道怎么写?