1701E - Text Editor - CodeForces Solution

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
 
void solve() {
    int N, M; cin >> N >> M;
    string s, t; cin >> s >> t;
    vector<vector<int>> left(N), right(N);
    for (int i = 0; i < N; i++) {
        left[i] = vector<int>(M);
        right[i] = vector<int>(M);
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            left[i][j] = s[i] == t[j] ? (i == 0 || j == 0 ? 0 : left[i - 1][j - 1]) + 1 : 0;
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        for (int j = M - 1; j >= 0; j--) {
            right[i][j] = s[i] == t[j] ? (i == N - 1 || j == M - 1 ? 0 : right[i + 1][j + 1]) + 1 : 0;
        }
    }
    vector<vector<bool>> lV(N), rV(N);
    for (int i = 0; i < N; i++) {
        lV[i] = vector<bool>(M);
        fill(all(lV[i]), false);
        rV[i] = vector<bool>(M);
        fill(all(rV[i]), false);
    }
    int k = -1;
    for (int j = 0; j < M; j++) {
        k++;
        while (k < N && s[k] != t[j]) k++;
        for (int i = k; i < N; i++) {
            lV[i][j] = true;
        }
    }
    k = N;
    for (int j = M - 1; j >= 0; j--) {
        k--;
        while (k >= 0 && s[k] != t[j]) k--;
        for (int i = 0; i <= k; i++) {
            rV[i][j] = true;
        }
    }
    if (!rV[0][0]) {
        cout << -1 << "\n";
        return;
    }
    int res = N - right[0][0];
    res = min(res, 1 + N - left[N - 1][M - 1] + (N - M));
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            if (lV[i - 1][j - 1] && rV[i][j]) {
                res = min(res, (N - i) - right[i][j] + 1 + (i - j) + (i - left[i - 1][j - 1]));
            }
        }
    }
    cout << res << "\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    for (int t = 0; t < T; t++) {
        solve();
    }
 
    return 0;
}