为了方便，我们记 \(T\) 为印章。
不可能出现上图的情况（或者说无效），区间都必须是左右端点严格递增的。
发现新增一个区间，无非就是放在上面/下面两种情况。
考虑用 \(f[i][j]\) 表示前 \(i\) 个字母全部匹配，且第 \(i\) 个字母恰好在最右侧的模式串的第 \(j\) 个位置是否可行。
三种方式：
-
直接从 \(f[i-1][j-1]\) 过来，不用新的印章，如
AB->ABC，f[3][3]|=f[2][2] -
用新的印章，盖在下层，如图，
绿线表示新的位置和印章中对应的位置。可以发现绿线可以对应印章中的任意一个位置，所以对于状态 \(f[i][m]\)（如上图蓝框内已经有一个右端点在 \(i\) 的印章了。\(i\) 必须匹配最后一个位置，因为新凸出的部分就是 \(m\) 的下一个位置），可以转移到所有 \(f[i+1][j](1\le j\le m)\)。 -
用新的印章，盖在上层，如图，
可以发现，这种情况对最后的印章位置没有要求，且新的匹配位置就是第一个位置，即 \(f[i][1]\leftarrow f[i-1][j]\)。
以上的转移均需满足对应位置字母相同。（画绿线的位置必须等于目标串的位置）
初始状态 \(f[1][1]=[s[1]=t[1]]\)
\(O(n(m-1)+nm)=O(nm)\)。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l,i##end=r;i<i##end;++i)
#define Rs(i,l,r) for(int i=l,i##end=r;i>i##end;--i)
#define Le(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define Re(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define L(i,l) for(int i=0,i##end=l;i<i##end;++i)
#define E(i,l) for(int i=1,i##end=l;i<=i##end;++i)
#define W(t) while(t--)
#define Wh while
const int N=200010,M=6;
int n,m;
bool f[N][M];
char s[N],t[M+1];
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>(s+1)>>(t+1);
f[1][1]=s[1]==t[1];
Le(i, 2, n)
E(j, m)
if(j==m){
E(k, m)
if(s[i]==t[k])f[i][k]|=f[i-1][j];
}
else{
if(s[i]==t[1])f[i][1]|=f[i-1][j];
if(s[i]==t[j+1])f[i][j+1]|=f[i-1][j];
}
cout<<(f[n][m]?"Yes":"No");
return 0;
}