fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. int dp[1025][1025];
  6.  
  7. void solve() {
  8.     string s1, s2;
  9.     cin >> s1 >> s2;
  10.     int n1 = s1.size(), n2 = s2.size();
  11.  
  12.     for (int i = 0; i <= n1; i++)
  13.         for (int j = 0; j <= n2; j++)
  14.             dp[i][j] = INF;
  15.     dp[0][0] = 0;
  16.  
  17.     for (int i = 0; i <= n1; i++) {
  18.         for (int j = 0; j <= n2; j++) {
  19.             if (i > 0)
  20.                 dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
  21.  
  22.             if (i == n1 || j == n2)
  23.                 continue;
  24.  
  25.             if (s1[i] == s2[j])
  26.                 dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
  27.             else
  28.                 dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);
  29.         }
  30.     }
  31.     cout << dp[n1][n2];
  32. }
  33.  
  34. int main() {
  35.     freopen("input.txt", "r", stdin);
  36.     freopen("output.txt", "w", stdout);
  37.     ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
  38.     cout.setf(ios::fixed), cout.precision(20);
  39.     solve();
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0s 4476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PhazQw
language:
C++14 (clang 8.0)
created:
4 years 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!