动态规划+前后缀预处理优化 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; } ```