//while(true)RP++; #include<bits/stdc++.h> using namespace std; const int N=1e6+10,MX=2e5; int n,m,a[N],b[N],s[N][30],f[N][2],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<<ans<<"\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; }*/ 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"; //cout<<(double)clock()/CLOCKS_PER_SEC; return 0; }