AT_abc452_d.[ABC452D] No-Subsequence Substring

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定由小写英文字母组成的字符串 SS 和 TT。

求 SS 的所有非空子串中,不包含 TT 作为(不一定连续的)子序列的子串个数。

这里,SS 的两个子串只要取出的位置不同,即使字符串内容相同也视为不同子串。

子串:字符串 XX 的子串是指从 XX 开头删除 00 个以上字符、从末尾删除 00 个以上字符后得到的字符串。

子序列:字符串 XX 的子序列是指从 XX 中删除 00 个以上元素后,剩余元素按原顺序排列得到的字符串。

输入格式

输入从标准输入以以下格式给出:

SS TT

输出格式

一行,输出答案。

输入输出样例

  • 输入#1

    abrakadabra
    aba

    输出#1

    51
  • 输入#2

    aaaaa
    a

    输出#2

    0
  • 输入#3

    rdddrdtdcdrrdcredctdordoeecrotet
    dcre

    输出#3

    263

说明/提示

样例解释 1

例如,SS 的第 11 个字符到第 33 个字符组成的子串 abr 不包含 TT 作为子序列。此外,k(仅 SS 的第 55 个字符)和 akada(SS 的第 44 个字符到第 88 个字符)等共 5151 个子串满足条件。

注意:abr 既可以作为 SS 的第 11 到 33 个字符的子串,也可以作为第 88 到 1010 个字符的子串,但由于取出位置不同,它们被视为不同的子串进行计数。

样例解释 2

SS 的所有非空子串都包含 TT 作为子序列。因此没有满足条件的子串,输出 00。

数据范围

  • SS 由小写英文字母组成

  • 记 ∣S∣|S| 为 SS 的长度,满足 1≤∣S∣≤2×1051 \le |S| \le 2 \times 10^5

  • TT 由小写英文字母组成

  • 记 ∣T∣|T| 为 TT 的长度,满足 1≤∣T∣≤501 \le |T| \le 50

输入解题思路,AI测评打分。不知道怎么写?

首页