#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define NUM 301
#define inf 1e9
#define MOD 1000000007
using namespace std;
bool pos;
vector <int> cpos[26];
int n, m;
ll res = inf;
string s1, s2;
void process (ll cposi, int idx2, ll cnt) {
if (cnt > res) return;
//cout << idx2 <<':'<< cpos[s2[idx2]-'A'][cposi] << endl;
if (idx2 == m - 1) {
//cout << cnt << endl << endl;
res = min(res, cnt);
return;
}
if (cpos[s2[idx2]-'A'][cposi] > 0) {
if(s1[cpos[s2[idx2]-'A'][cposi] - 1] == s2[idx2 + 1]) {
//cout << '+';
process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi] - 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + 1);
}
}
if (cpos[s2[idx2]-'A'][cposi] < n - 1) {
if(s1[cpos[s2[idx2]-'A'][cposi] + 1] == s2[idx2 + 1]) {
process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi] + 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + 1);
}
}
int sz = cpos[s2[idx2]-'A'].size ();
for (int i = 1; i < max(cposi + 1, sz - cposi); i ++) {
if (cposi - i >= 0) {
if (cpos[s2[idx2]-'A'][cposi - i] > 0) {
if(s1[cpos[s2[idx2]-'A'][cposi - i] - 1] == s2[idx2 + 1]) {
//cout << '-';
process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi - i] - 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi - i] - cpos[s2[idx2]-'A'][cposi]) + 1);
}
}
if (cpos[s2[idx2]-'A'][cposi - i] < n - 1) {
if(s1[cpos[s2[idx2]-'A'][cposi - i] + 1] == s2[idx2 + 1]) {
//cout << '-';
process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi - i] + 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi - i] - cpos[s2[idx2]-'A'][cposi]) + 1);
}
}
}
if (cposi + i < cpos[s2[idx2]-'A'].size ()) {
if (cpos[s2[idx2]-'A'][cposi + i] > 0) {
if(s1[cpos[s2[idx2]-'A'][cposi + i] - 1] == s2[idx2 + 1]) {
//cout << '-';
process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi + i] - 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi + i] - cpos[s2[idx2]-'A'][cposi]) + 1);
}
}
if (cpos[s2[idx2]-'A'][cposi + i] < n - 1) {
if(s1[cpos[s2[idx2]-'A'][cposi + i] + 1] == s2[idx2 + 1]) {
//cout << '-';
process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi + i] + 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi + i] - cpos[s2[idx2]-'A'][cposi]) + 1);
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
cin >> s1 >> s2;
for (int i = 0; i < n; i ++) {
cpos [s1[i]-'A'].push_back(i);
}
for (int i = 0; i < cpos[s2[0]-'A'].size (); i ++) {
process (i, 0, 0);
}
cout << endl;
if (res != inf) {
cout << res;
}
else {
cout << -1;
}
}
Compilation message
bajka.cpp: In function 'void process(long long int, int, long long int)':
bajka.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (cposi + i < cpos[s2[idx2]-'A'].size ()) {
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp: In function 'int main()':
bajka.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < cpos[s2[0]-'A'].size (); i ++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
