线性dp：P2679 子串
1.P2679 子串
传送门
https://www.luogu.com.cn/problem/P2679这道题是公共子串问题的变种，但是我第一时间确实没想到转移方程（写少了）
一开始看了题解也没太看懂，直到自己模拟一遍（模拟数据便于理解原理）下面是感悟
这道题我最初的疑惑点在于究竟是定住a串找b串，还是定住b串找a串。我在一开始的想法是定住b串找a串，因为这道题我们想要用a串中的子串来匹配b串。但是后来我发现这不可行，因为a串只能按照顺序来找，如果定住b串，就不能保证后面补充的是从前面来的了，如此一来并不好操作（子串间连接顺序不同）。
这里还用到了一个优化，把第一维a串的遍历省掉了，因为每一次只与前一个位置的有关
下面直接用代码来解释（有注释）
Welcome - Luogu Spilopelia 配合这个食用
图摘自https://www.luogu.com.cn/article/k0zkdin9
// Problem:
// P2679 [NOIP2015 提高组] 子串
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2679
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
using namespace std;
int f[2][205][205][2];//这个和上一个 / 匹配的m / 多少个子串 / 用或者不用这个a[i]
char a[1005],b[205];
const int P=1000000007;int main(){int n,m,k;cin>>n>>m>>k;cin>>(a+1)>>(b+1);f[0][0][0][0]=1;f[1][0][0][0]=1; //不用a[i]满足0个b对应x个a的情况（0<=x<=n）这里x被简化成0/1了for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){for(int p=1;p<=k;++p){if(a[i]==b[j]){//如果这两个匹配f[i%2][j][p][1]=((f[(i-1)%2][j-1][p][1]+f[(i-1)%2][j-1][p-1][1])%P+f[(i-1)%2][j-1][p-1][0]%P)%P;f[i%2][j][p][0]=(f[(i-1)%2][j][p][0]+f[(i-1)%2][j][p][1])%P;}else{f[i%2][j][p][1]=0;f[i%2][j][p][0]=(f[(i-1)%2][j][p][0]+f[(i-1)%2][j][p][1])%P;//用这里收割从前面来的子串}}}}cout<<(f[n%2][m][k][0]+f[n%2][m][k][1])%P;return 0;
}