D - No-Subsequence Substring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

英小文字からなる文字列 S,T が与えられます。

S の空でない部分文字列 s のうち、T を（連続するとは限らない）部分列として含まないものの個数を求めてください。

ここで、S の 2 つの部分文字列は、取り出した箇所が異なれば文字列として等しくても区別するものとします。

部分文字列とは 文字列 X の部分文字列とは、X の先頭から 0 文字以上、末尾から 0 文字以上を削除して得られる文字列のことを指します。
部分列とは 文字列 X の部分列とは，X の要素を 0 個以上選んで削除し，残った要素を元の順序を保って並べた文字列のことを指します．

制約

  • S は英小文字からなる文字列
  • |S| を S の長さとして、1\le |S|\le2\times10 ^ 5
  • T は英小文字からなる文字列
  • |T| を T の長さとして、1\le |T|\le50

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

答えを出力せよ。

入力例 1

abrakadabra
aba

出力例 1

51

例えば、S の 1 文字目から 3 文字目までからなる部分文字列 abr は T を部分列として含みません。 他にも、k（S の 5 文字目のみ）や akada（S の 4 文字目から 8 文字目）などの 51 個の部分文字列が条件を満たします。

文字列 abr は S の 1 文字目から 3 文字目までからなる部分文字列としても S の 8 文字目から 10 文字目までからなる部分文字列としても得ることができますが、文字列から取り出す箇所が異なるため区別して数えることに注意してください。

入力例 2

aaaaa
a

出力例 2

0

S の空でない部分文字列は、すべて T を部分列として含みます。

よって、条件を満たす部分文字列は存在しないため、0 を出力してください。

入力例 3

rdddrdtdcdrrdcredctdordoeecrotet
dcre

出力例 3

263

Score : 400 points

Problem Statement

You are given strings S and T consisting of lowercase English letters.

Among the non-empty substrings s of S, count those that do not contain T as a (not necessarily contiguous) subsequence.

Here, two substrings of S are distinguished if they are taken from different positions, even if they are equal as strings.

What is a substring? A substring of a string X is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of X.
What is a subsequence? A subsequence of a string X is a string obtained by deleting zero or more elements from X and arranging the remaining elements in their original order.

Constraints

  • S is a string consisting of lowercase English letters.
  • 1\le |S|\le2\times10 ^ 5, where |S| is the length of S.
  • T is a string consisting of lowercase English letters.
  • 1\le |T|\le50, where |T| is the length of T.

Input

The input is given from Standard Input in the following format:

S
T

Output

Output the answer.

Sample Input 1

abrakadabra
aba

Sample Output 1

51

For example, the substring abr consisting of the first through third characters of S does not contain T as a subsequence. Including this, there are 51 substrings satisfying the condition, such as k (only the fifth character of S) and akada (the fourth through eighth characters of S).

Note that the string abr can be obtained both as the substring from the first to third characters of S and as the substring from the eighth to tenth characters of S, but they are taken from different positions, so they are counted separately.

Sample Input 2

aaaaa
a

Sample Output 2

0

All non-empty substrings of S contain T as a subsequence.

Thus, there are no substrings satisfying the condition, so output 0.

Sample Input 3

rdddrdtdcdrrdcredctdordoeecrotet
dcre

Sample Output 3

263