//while(true)RP++; #include<bits/stdc++.h> using namespace std; const int N=1e6+10,MX=2e5,M=1e3+10; int n,m,a[N],b[N],s[N][30],f[M][M],g[N],c[N],ans; string s1,s2; int main() { //freopen("match.in","r",stdin); //freopen("match.out","w",stdout); cin>>n>>m; cin>>s1>>s2; memset(s,0x3f,sizeof(s)); bool flag=1; for(int i=1;i<=n;++i) { a[i]=s1[i-1]-'A'+1; if(i>1&&a[i-1]!=a[i]) { flag=0; } } for(int i=1;i<=m;++i) { b[i]=s2[i-1]-'A'+1; } if(flag) { for(int i=1;i<=m;++i) { if(b[i]==a[1]) { ans++; } } cout<<min(ans,n)<<"\n"; return 0; } if(m>MX) { for(int i=1,j=1;i<s2.size();i++,j++) { if(rand()%m>=MX) { j--,m--; } else { b[j]=s2[i]-'A'+1; } } } for(int i=m;i>=1;--i) { for(int j=1;j<=26;j++) { s[i][j]=s[i+1][j]; } s[i][b[i]]=i; } memset(f,0x3f,sizeof(f)); f[0][0]=0; for(int j=1;j<=n;++j) { for(int i=1;i<=n;++i) { f[i][j]=f[i][j-1]; if(f[i-1][j-1]<1e9) { f[i][j]=min(f[i][j],s[f[i-1][j-1]][a[j]]);//cout<<s[f[i-1][j-1]][a[j]]<<" "; } if(f[i][j]<1e9)ans=max(ans,i); } //cout<<'\n'; } cout<<ans<<"\n"; //cout<<(double)clock()/CLOCKS_PER_SEC; return 0; }