//while(true)RP++; #include<bits/stdc++.h> using namespace std; const int N=1e6+10,MX=1e9,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("match1.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<=1e3) { for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { f[j][i&1]=max(f[j-1][i&1],f[j][~i&1]); if(a[i]==b[j]) { f[j][i&1]=max(f[j][i&1],f[j-1][~i&1]+1); //cout<<f[j-1][~i&1]+1<<"\n"; } ans=max(ans,f[j][i&1]); } } cout<<ans<<"\n"; return 0; } for(int i=m;i>=0;--i) { for(int j=1;j<=26;j++) { s[i][j]=s[i+1][j]; } s[i][b[i]]=i; }/* cout<<s[1][1]<<"\n"; return 0;*/ memset(f,0x3f,sizeof(f)); f[0][0]=0; for(int j=1;j<=n;++j) { f[0][j]=0; for(int i=1;i<=j;++i) { f[i][j]=f[i][j-1]; if(f[i-1][j-1]<MX) { 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]<MX)ans=max(ans,i); } //cout<<'\n'; } cout<<ans<<"\n"; //cout<<(double)clock()/CLOCKS_PER_SEC; return 0; }