This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >>n >> m;
string s, t;
cin >> s >> t;
vector <int> pos[26];
for(int i = 0; i < n; i++)
{
pos[s[i] - 'a'].push_back(i);
}
vector <vector <int> > dp(m, vector <int> (n, 1e9));
for(int i = 0; i < pos[t[0] - 'a'].size(); i++)
{
int ind = pos[t[0] - 'a'][i];
dp[0][ind] = 1;
}
for(int it = 1; it < m; it++)
{
int i1 = t[it - 1] - 'a';
int minval = 1e9;
int en = -1;
for(int i = 0; i < pos[i1].size(); i++)
{
int ind = pos[i1][i];
minval += ind - en;
minval = min(minval, dp[it - 1][ind]);
if(ind > 0 && s[ind - 1] == t[it])
{
dp[it][ind - 1] = min(dp[it][ind - 1], minval + 1);
}
if(ind < n - 1 && s[ind + 1] == t[it])
{
dp[it][ind + 1] = min(dp[it][ind + 1], minval + 1);
}
en = ind;
}
minval = 1e9;
en = 1e9;
for(int i = pos[i1].size() - 1;i >= 0; i--)
{
int ind = pos[i1][i];
minval += en - ind;
minval = min(minval, dp[it - 1][ind]);
if(ind > 0 && s[ind - 1] == t[it])
{
dp[it][ind - 1] = min(dp[it][ind - 1], minval + 1);
}
if(ind < n - 1 && s[ind + 1] == t[it])
{
dp[it][ind + 1] = min(dp[it][ind + 1], minval + 1);
}
en = ind;
}
}
int ans = 1e9;
for(int i = 0; i < n; i++)
{
ans = min(ans, dp[m - 1][i] - 1);
}
if(ans == 1e9)
{
ans = -1;
}
cout << ans;
return 0;
}
Compilation message (stderr)
bajka.cpp: In function 'int main()':
bajka.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < pos[t[0] - 'a'].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0; i < pos[i1].size(); i++)
| ~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |