#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; using i64 = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; string S1, S2; cin >> n >> m >> S1 >> S2; S1 = '#' + S1; S2 = '#' + S2; vector<int> idxs[26]; for (int i = 1; i <= m; ++i) idxs[S2[i] - 'A'].push_back(i); vector<vector<int>> f(n + 1, vector<int>(n + 1, m + 1)); f[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= n; ++j) { f[i][j] = f[i - 1][j]; if (j == 0) continue; const auto& idx = idxs[S1[i] - 'A']; auto match = upper_bound(idx.begin(), idx.end(), f[i - 1][j - 1]); if (match != idx.end()) f[i][j] = min(f[i][j], *match); } } for (int i = n; i >= 0; --i) { if (f[n][i] <= m) { cout << i << endl; break; } } return 0; }