#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define double long double
using namespace std;
void db() {cerr << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {
cerr << a << ' ', db(b...);
}
const int N = 100, inf = 1e9 + 1;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
int dp[m][n], ans = inf;
for (int i = 0; i < n; i++)
if (s[i] == t[0])
dp[0][i] = 0;
else
dp[0][i] = inf;
for (int i = 1; i < m; i++){
for (int j = 0; j < n; j++){
dp[i][j] = inf;
if (s[j] != t[i])
continue;
if (j)
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
if (j < n - 1)
dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + 1);
}
int mi = inf;
for (int j = 0; j < n; j++){
if (s[j] != t[i])
continue;
dp[i][j] = min(dp[i][j], j + mi);
mi = min(mi, dp[i][j] - j);
}
mi = inf;
for (int j = n - 1; j >= 0; j--){
if (s[j] != t[i])
continue;
dp[i][j] = min(dp[i][j], -j + mi);
mi = min(mi, dp[i][j] + j);
//db(i, j, dp[i][j]);
}
}
for (int &i : dp[m - 1])
ans = min(ans, i);
cout << (ans < inf ? ans : -1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
