Edit distance

#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
using namespace std;
int main(){
  priority_queue<tuple<int,unsigned,string>> eq;
  set<string> v;
  string q;
  int d;
  unsigned l;
  string a;
  cin>>a>>q;
  while(l<q.size()&&l<a.size()&&a[l]==q[l])l++;
  eq.emplace(0,l,a);
  while(true){
    tie(d,l,a) = eq.top();
    d = -d;
    eq.pop();
    if(v.count(a))continue;
    v.insert(a);
    while(l<q.size()&&l<a.size()&&a[l]==q[l])l++;
    if(l==q.size()){
      if(a.size()>l){
        eq.emplace(-(d+a.size()-l),l,q);
        continue;
      }
      break;
    }
    if(a.size()==l){
      eq.emplace(-(d+q.size()-a.size()),q.size(),q);
      continue;
    }
    eq.emplace(-d-1,l+1,a.substr(0,l)+q[l]+a.substr(l));
    a[l]=q[l];
    eq.emplace(-d-1,l+1,a);
    auto k = a.find(q[l],l+1);
    if(k==string::npos)continue;
    eq.emplace(-(d+k-l),l+1,a.substr(0,l)+a.substr(k));
  }
  cout<<d<<'\n';
}

Test 1

Verdict: UNKNOWN

Test 2

Verdict: UNKNOWN

Test 3

Verdict: UNKNOWN

Test 4

Verdict: UNKNOWN

Test 5

Verdict: UNKNOWN

Test 6

Verdict: UNKNOWN

Test 7

Verdict: UNKNOWN

Test 8

Verdict: UNKNOWN

Test 9

Verdict: UNKNOWN

Test 10

Verdict: UNKNOWN

Test 11

Verdict: UNKNOWN

Test 12

Verdict: UNKNOWN

Test 13

Verdict: UNKNOWN

Test 14

Verdict: UNKNOWN

Test 15

Verdict: UNKNOWN

Test 16

Verdict: UNKNOWN

Test 17

Verdict: UNKNOWN

Test 18

Verdict: UNKNOWN

Test 19

Verdict: UNKNOWN