fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Samurai ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  4. string a,b,c; vector<vector<int>>dp;
  5. int rec(int i=0, int j=0){
  6.     if(i==a.size() && j==b.size()) return 0;
  7.     int &ret = dp[i][j];
  8.     if(~ret) return ret;
  9.     ret = INT_MAX;
  10.     if(i<a.size()){
  11.         if(a[i] == c[i+j]) ret = rec(i+1,j);
  12.         else ret = 1 + rec(i+1,j);
  13.     }
  14.     if(j<b.size()){
  15.         if(b[j] == c[i+j]) ret = min(ret, rec(i,j+1));
  16.         else ret = min(ret, 1 + rec(i,j+1));
  17.     }
  18.     return ret;
  19. }
  20. int main(){ Samurai
  21.     int _t = 1;
  22.     cin >> _t;
  23.     for (int i = 1; i <= _t; i++){
  24.         cin >> a >> b >> c;
  25.         dp = vector<vector<int>>(a.size()+5,vector<int>(b.size()+5,-1));
  26.         cout << rec() << '\n';
  27.     }
  28.     return 0;
  29. }
  30.  
  31.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/6eix3j
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!