动态规划+前后缀预处理优化
dp[i][j] 为，匹配到t串的第i个字符，且当前在s串下标j的最小路程和，（转为滚动数组）

#include <bits/stdc++.h>

using namespace std;


const int INF = 1e9;


int main() {

    ios::sync\_with\_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);


    ios::sync\_with\_stdio(false);


    int n, m, l;

    string s, t;

    cin >> n >> m >> l;

    cin >> s >> t;


    vector<vector<int>> mp(26);

    for (int i = 0; i < n; ++i) {

        mp[s[i] - 'a'].push\_back(i);

    }


    // 初始化滚动数组

    vector<int> prev\_dp(n, INF);

    int first\_char = t[0] - 'a';

    for (int pos : mp[first\_char]) {

        prev\_dp[pos] = 0;

    }


    int ans = 1; // 至少能匹配第一个字符


    for (int i = 1; i < m; ++i) {

        int curr\_c = t[i] - 'a';

        int prev\_c = t[i-1] - 'a';

        auto& prev\_pos = mp[prev\_c];

        auto& curr\_pos = mp[curr\_c];


        if (prev\_pos.empty() || curr\_pos.empty()) break;


        // 预处理前缀最小值和后缀最小值

        int k\_prev = prev\_pos.size();

        vector<int> prefix\_min(k\_prev, INF);

        vector<int> suffix\_min(k\_prev, INF);


        // 计算前缀最小值（dp[p] - p）

        int min\_val = INF;

        for (int k = 0; k < k\_prev; ++k) {

            int p = prev\_pos[k];

            min\_val = min(min\_val, prev\_dp[p] - p);

            prefix\_min[k] = min\_val;

        }


        // 计算后缀最小值（dp[p] + p）

        min\_val = INF;

        for (int k = k\_prev - 1; k >= 0; --k) {

            int p = prev\_pos[k];

            min\_val = min(min\_val, prev\_dp[p] + p);

            suffix\_min[k] = min\_val;

        }


        vector<int> curr\_dp(n, INF);

        bool found = false;


        for (int j : curr\_pos) {

            // 寻找最大的k <= j

            auto it = upper\_bound(prev\_pos.begin(), prev\_pos.end(), j);

            int idx = it - prev\_pos.begin() - 1;


            int left\_cost = INF;

            if (idx >= 0) {

                left\_cost = prefix\_min[idx] + j;

            }


            // 寻找最小的k >= j

            it = lower\_bound(prev\_pos.begin(), prev\_pos.end(), j);

            int idx2 = it - prev\_pos.begin();

            int right\_cost = INF;

            if (idx2 < k\_prev) {

                right\_cost = suffix\_min[idx2] - j;

            }


            int best = min(left\_cost, right\_cost);

            if (best <= l) {

                curr\_dp[j] = best;

                found = true;

            }

        }


        if (found) {

            ans = i + 1; // 更新最大匹配长度

            prev\_dp.swap(curr\_dp);

        } else {

            break; // 无法继续匹配，提前终止

        }

    }


    cout << ans << '\\n';

    return 0;

}