https://www.luogu.com.cn/problem/P2679
只能说是，超级好的一道例题

[NOIP2015 提高组] 子串

题目背景

NOIP2015 Day2T2

题目描述

有两个仅包含小写英文字母的字符串 \(A\) 和 \(B\)。

现在要从字符串 \(A\) 中取出 \(k\) 个互不重叠的非空子串，然后把这 \(k\) 个子串按照其在字符串 \(A\) 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 \(B\) 相等？

注意：子串取出的位置不同也认为是不同的方案。

由于答案可能很大，所以这里要求输出答案对 \(1000000007\) 取模的结果。

样例 #1

样例输入 #1

6 3 1 
aabaab 
aab

样例输出 #1

2

数据范围

对于第 1 组数据：\(1≤n≤500,1≤m≤50,k=1\);
对于第 2 组至第 3 组数据：\(1≤n≤500,1≤m≤50,k=2\);
对于第 4 组至第 5 组数据：\(1≤n≤500,1≤m≤50,k=m\);
对于第 1 组至第 7 组数据：\(1≤n≤500,1≤m≤50,1≤k≤m\);
对于第 1 组至第 9 组数据：\(1≤n≤1000,1≤m≤100,1≤k≤m\);
对于所有 10 组数据：\(1≤n≤1000,1≤m≤200,1≤k≤m\)。

分析：
定义状态f[i][j][k][0/1]表示字符串A的前i个字符和字符串B的前j个字符用了k个子串，第四维为1表示A字符串的第i个字符必须用，为0表示A字符串的第i个字符不能用，匹配上的方案数。

可以分析出当a[i] == b[j]时，可以拼到a[i-1],b[j-1]之后(a[i-1] == b[j-1])，不再多开一个子串；也可以多开一个。当a[i-1] != b[j-1]，则必须多开一个子串。
f[i][j][k][1] =f[i-1][j-1][k-1][1] + f[i-1][j-1][k][1] + f[i-1][j-1][k-1][0];
当a[i] != b[j]时，
f[i][j][k][1] = 0;

考虑f[i][j][k][0]，也就是不管a[i]和b[j]相不相同，a[i]都不使用,还得匹配的上，说明b[j]一定

特别注意的是边界：