3905: 张老师的次完美彩带
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
张老师有一根彩带，这根彩带上一共有 $26$ 种不同的颜色，并且彩带均匀的分割成了 $n$ 块长度为 $1$ 的部分，每一块都有一种颜色，从左往右数第 $i$ 块的颜色用 $a_i$ 来表示
现在张老师希望能够得到一根完美的彩带，这根彩带的长度为 $m$ ，并且颜色依次为 $b_i$
但是张老师很懒，他懒得专门切那么多刀去得到这根完美的彩带，于是他决定——只切最多两刀！
也就是张老师可以选择以下四种方案之一：
1. 在某个位置切一刀，丢掉左边的部分，保留右边的部分
2. 在某个位置切一刀，丢掉右边的部分，保留左边的部分
3. 选择两个位置分别切一刀，然后保留中间的部分
4. 一刀都不切
但是这样切出来的彩带不一定是完美的彩带，但是没有关系
张老师认为只要切出来的彩带中依次包含着 $b_i$（可以不连续）那么这根彩带就是次完美的彩带，也能接受！
例如 $b=abcd$，那么对于 $s=abccd,adbdcd$ 都是满足的
现在张老师想知道，他一共有多少种切法能够得到次完美或者完美的彩带？
现在张老师希望能够得到一根完美的彩带，这根彩带的长度为 $m$ ，并且颜色依次为 $b_i$
但是张老师很懒，他懒得专门切那么多刀去得到这根完美的彩带，于是他决定——只切最多两刀！
也就是张老师可以选择以下四种方案之一：
1. 在某个位置切一刀，丢掉左边的部分，保留右边的部分
2. 在某个位置切一刀，丢掉右边的部分，保留左边的部分
3. 选择两个位置分别切一刀，然后保留中间的部分
4. 一刀都不切
但是这样切出来的彩带不一定是完美的彩带，但是没有关系
张老师认为只要切出来的彩带中依次包含着 $b_i$（可以不连续）那么这根彩带就是次完美的彩带，也能接受！
例如 $b=abcd$，那么对于 $s=abccd,adbdcd$ 都是满足的
现在张老师想知道，他一共有多少种切法能够得到次完美或者完美的彩带？
输入
输入第一行包含两个整数 $n,m$，含义如题
输入第二行包含一个字符串 $a$，依次表示原彩带的颜色，其中每种颜色用一个小写字母表示
输入第三行包含一个字符串 $b$，依次表示完美彩带的颜色，其中每种颜色用一个小写字母表示
| 数据点编号 | $n$ | $m$ |
| :---: | :---: | :---: |
| $1$ | $1 \leq n \leq 10$ | $1 \leq m \leq 10$ |
| $2$ | $1 \leq n \leq 100$ | $1 \leq m \leq 100$ |
| $3 \sim 6$ | $1 \leq n \leq 1000$ | $1 \leq m \leq 100$ |
| $7 \sim 8$ | $1 \leq n \leq 10^5$ | $1 \leq m \leq 100$ |
| $9 \sim 10$ | $1 \leq n \leq 3*10^5$ | $1 \leq m \leq 100$ |
输入第二行包含一个字符串 $a$，依次表示原彩带的颜色，其中每种颜色用一个小写字母表示
输入第三行包含一个字符串 $b$，依次表示完美彩带的颜色，其中每种颜色用一个小写字母表示
| 数据点编号 | $n$ | $m$ |
| :---: | :---: | :---: |
| $1$ | $1 \leq n \leq 10$ | $1 \leq m \leq 10$ |
| $2$ | $1 \leq n \leq 100$ | $1 \leq m \leq 100$ |
| $3 \sim 6$ | $1 \leq n \leq 1000$ | $1 \leq m \leq 100$ |
| $7 \sim 8$ | $1 \leq n \leq 10^5$ | $1 \leq m \leq 100$ |
| $9 \sim 10$ | $1 \leq n \leq 3*10^5$ | $1 \leq m \leq 100$ |
输出
输出一个整数，表示张老师一共有多少种不同的切彩带方案
其中，如果是切两刀的方案，两刀不分先后，即先切 $i$ 再切 $j$ 和先切 $j$ 再切 $i$ 属于同一种方案
其中，如果是切两刀的方案，两刀不分先后，即先切 $i$ 再切 $j$ 和先切 $j$ 再切 $i$ 属于同一种方案
样例输入 复制
8 3
abczdefg
zfg样例输出 复制
4提示
样例解释1
1. 一刀都不切
2. 在 `ab` 之间切一刀，丢掉左边部分
3. 在 `bc` 之间切一刀，丢掉左边部分
4. 在 `cz` 之间切一刀，丢掉左边部分
样例解释2
1. 一刀都不切
2. 在 `ab` 之间切一刀，丢掉左边部分
3. 在 `bc` 之间切一刀，丢掉左边部分
4. 在 `dd` 之间切一刀，丢掉右边部分
5. 在 `ab` 和 `dd` 之间切一刀，保留中间部分
6. 在 `bc` 和 `dd` 之间切一刀，保留中间部分
1. 一刀都不切
2. 在 `ab` 之间切一刀，丢掉左边部分
3. 在 `bc` 之间切一刀，丢掉左边部分
4. 在 `cz` 之间切一刀，丢掉左边部分
1. 一刀都不切
2. 在 `ab` 之间切一刀，丢掉左边部分
3. 在 `bc` 之间切一刀，丢掉左边部分
4. 在 `dd` 之间切一刀，丢掉右边部分
5. 在 `ab` 和 `dd` 之间切一刀，保留中间部分
6. 在 `bc` 和 `dd` 之间切一刀，保留中间部分