SHARE
TWEET

Untitled

a guest Sep 23rd, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Edit Distance Bottom-Up
  2. //https://www.spoj.com/problems/EDIST/
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int main(){
  7.     int n;
  8.     ios_base::sync_with_stdio(false);
  9.     cin >> n;
  10.     while(n--){
  11.         string a, b;
  12.         cin >> a >> b;
  13.         vector<vector<int> > mat(a.size()+1, vector<int>(b.size()+1));
  14.         for(int i = 1; i <= a.size(); ++i){
  15.             mat[i][0] = i;
  16.         }
  17.         for(int i = 1; i <= b.size(); ++i){
  18.             mat[0][i] = i;
  19.         }
  20.         for(int i = 1; i <= a.size(); ++i){
  21.             for(int j = 1; j <= b.size(); ++j){
  22.                 if(a[i-1] == b[j-1]){
  23.                     mat[i][j] = mat[i-1][j-1];
  24.                 }
  25.                 else mat[i][j] = min(mat[i-1][j-1], min(mat[i][j-1], mat[i-1][j])) + 1;
  26.             }
  27.         }
  28.         cout << mat[a.size()][b.size()] << '\n';
  29.     }
  30. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top