Double-ended Strings Solution Codeforces Round #710 Div. 3

by

You are given the strings aa and bb, consisting of lowercase Latin letters. You can do any number of the following operations in any order:

  • if |a|>0|a|>0 (the length of the string aa is greater than zero), delete the first character of the string aa, that is, replace aa with a2a3…ana2a3…an;
  • if |a|>0|a|>0, delete the last character of the string aa, that is, replace aa with a1a2…an−1a1a2…an−1;
  • if |b|>0|b|>0 (the length of the string bb is greater than zero), delete the first character of the string bb, that is, replace bb with b2b3…bnb2b3…bn;
  • if |b|>0|b|>0, delete the last character of the string bb, that is, replace bb with b1b2…bn−1b1b2…bn−1.

Note that after each of the operations, the string aa or bb may become empty.

For example, if a=a=”hello” and b=b=”icpc”, then you can apply the following sequence of operations:

  • delete the first character of the string aa ⇒⇒ a=a=”ello” and b=b=”icpc”;
  • delete the first character of the string bb ⇒⇒ a=a=”ello” and b=b=”cpc”;
  • delete the first character of the string bb ⇒⇒ a=a=”ello” and b=b=”pc”;
  • delete the last character of the string aa ⇒⇒ a=a=”ell” and b=b=”pc”;
  • delete the last character of the string bb ⇒⇒ a=a=”ell” and b=b=”p”.

For the given strings aa and bb, find the minimum number of operations for which you can make the strings aa and bb equal. Note that empty strings are also equal.Input

The first line contains a single integer tt (1≤t≤1001≤t≤100). Then tt test cases follow.

The first line of each test case contains the string aa (1≤|a|≤201≤|a|≤20), consisting of lowercase Latin letters.

The second line of each test case contains the string bb (1≤|b|≤201≤|b|≤20), consisting of lowercase Latin letters.Output

For each test case, output the minimum number of operations that can make the strings aa and bb equal.Exampleinput

5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser

output

0
2
13
3
20

Solution :

#include <bits/stdc++.h>

#define TRACE(x) cerr << #x << ” = ” << x << endl

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define FOR(i, a, b) for(int i = (a); i < (b); i++)

#define REP(i, n) FOR(i, 0, n)

#define SZ(x) (int)(x).size()

using namespace std;

typedef long long ll;

typedef double lf;

typedef pair<int, int> pii;

typedef vector<int> VI;

template<class Num>

Num mabs(Num A){

if(A < 0) return -A;

return A;

}

 

const int inf = (int)2e9;

 

string a, b;

 

bool ok(int i, int j, int ii, int jj){

string ta = a, tb = b;

REP(k, j) ta.pop_back();

REP(k, jj) tb.pop_back();

reverse(ta.begin(), ta.end());

reverse(tb.begin(), tb.end());

REP(k, i) ta.pop_back();

REP(k, ii) tb.pop_back();

if(ta == tb) return true;

return false;

}

 

void solve(){

cin >> a >> b;

int n = SZ(a), m = SZ(b);

int ans = n + m;

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

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

for(int ii = 0; ii <= m; ii++){

for(int jj = 0; jj <= m; jj++){

if(i + j > n || ii + jj > m) continue;

if(i + j + ii + jj > ans) continue;

if(ok(i, j, ii, jj))

ans = min(ans, i + j + ii + jj);

}

}

}

}

 

cout << ans << ‘\n’;

}

 

int main(){

int t;

scanf(“%d”, &t);

while(t–)

solve();

return 0;

}

Leave a Comment