题目描述

给定一个字符串 $S$ 和一个字符串 $T$，你可以从 $S$ 中删除一段头或者一段尾。

特别的，你可以选择仅删除头，或者仅删除尾，或者头尾都删除，或者头尾都不删除。

请问你有多少种删法可以使得剩余的子串 $X$ 包含 $T$ 的所有字符，并且保证 $T$ 是 $X$ 的一个子序列。

输入格式

给定两行字符串，第一行是字符串 $S$，第二行是字符串 $T$。

输出格式

输出一个数字，表示答案。

abctdefg
tfg

4

abcbcd
bcd

4

说明/提示

样例解释 #1

对于字符串abctdefg，有如下删头去尾的子串包含tfg的所有字符，并且tfg是其子序列：abctdefg、bctdefg、ctdefg、tdefg总共四个。

数据范围

每组数据点 $10$ 分，共 $10$ 组数据。

其中 $n$ 表示字符串 $S$ 的长度， $m$ 表示字符串 $T$ 的长度

大样例

大样例下载