Description

[LeetCode 115]

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

Input Format

输入第一行包括两个正整数N，M，分别为S与T的长度（1 ≤ S,T ≤ 1000）

第二行S

第三行T

Output Format

输出一个正整数，S 的子序列中 T 出现的个数

7 6
rabbbit
rabbit​

3​

Hint

样例2:

输入：S="babgbag", T = "bag"

输出：5

注意：答案可能很大

Source

动态规划 串 基础百练