fork download
copy 
  1. #include <iostream>
  2. #include <cctype>
  3. using namespace std;
  4.  
  5. int min(int a, int b) 
  6. {
  7.     if (a < b)
  8.         return a;
  9.     else
  10.         return b;
  11. }
  12.  
  13. int main() 
  14. {
  15.     string s1, s2;
  16.  
  17.     cout << "Hello, Welcome to the Edit Distance Demonstration" << endl;
  18.     cout << "=====================================================" << endl;
  19.     cout << "Please input the first word: ";
  20.     cin >> s1;
  21.     cout << "Please input the second word: ";
  22.     cin >> s2;
  23.  
  24.     int l1 = s1.size(), l2 = s2.size();
  25.     int edit_dist[1000][1000];
  26.  
  27.     for (int i = 0; i <= l1; i++) 
  28.     {
  29.         for (int j = 0; j <= l2; j++)
  30.         {
  31.             if (i == 0)
  32.                 edit_dist[i][j] = j;
  33.             else if (j == 0)
  34.                 edit_dist[i][j] = i;
  35.             else if (s1[i - 1] == s2[j - 1]) 
  36.             {
  37.                 edit_dist[i][j] = edit_dist[i - 1][j - 1];
  38.             } else
  39.                 edit_dist[i][j] = 1 + min(edit_dist[i][j - 1], min(edit_dist[i - 1][j], edit_dist[i - 1][j - 1]));
  40.         }
  41.     }
  42.  
  43.     cout << "The Output Matrix:" << endl;
  44.     cout << "+";
  45.     for (int j = 0; j <= l2; j++) 
  46.     {
  47.         cout << "----+";
  48.     }
  49.     cout << endl;
  50.     for (int i = 0; i <= l1; i++) 
  51.     {
  52.         cout << "| ";
  53.         for (int j = 0; j <= l2; j++) 
  54.         {
  55.             cout << edit_dist[i][j] << " | ";
  56.         }
  57.         cout << endl;
  58.         cout << "+";
  59.         for (int j = 0; j <= l2; j++) 
  60.         {
  61.             cout << "----+";
  62.         }
  63.         cout << endl;
  64.     }
  65.  
  66.     cout << "The edit distance is: " << edit_dist[l1][l2] << endl;
  67.  
  68.     // Alignment
  69.     cout << "Alignment is: ";
  70.     int i = l1, j = l2;
  71.     while (i > 0 && j > 0) 
  72.     {
  73.         if (s1[i - 1] == s2[j - 1]) 
  74.         {
  75.             cout << s1[i - 1];
  76.             i--;
  77.             j--;
  78.         } else if (edit_dist[i][j] == edit_dist[i - 1][j - 1] + 1) 
  79.         {
  80.             cout << s1[i - 1];
  81.             i--;
  82.             j--;
  83.         } else if (edit_dist[i][j] == edit_dist[i][j - 1] + 1) 
  84.         {
  85.             cout << "_";
  86.             j--;
  87.         } else 
  88.         {
  89.             cout << "_";
  90.             i--;
  91.         }
  92.     }
  93.     while (i > 0) 
  94.     {
  95.         cout << s1[i - 1];
  96.         i--;
  97.     }
  98.     while (j > 0) 
  99.     {
  100.         cout << "_";
  101.         j--;
  102.     }
  103.     cout << endl;
  104.  
  105.     return 0;
  106. }
  107.  
  108.  
  109.  
Success #stdin #stdout 0.01s 5244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Hello, Welcome to the Edit Distance Demonstration
=====================================================
Please input the first word: Please input the second word: The Output Matrix:
+----+
| 0 | 
+----+
The edit distance is: 0
Alignment is:
https://ideone.com/MFhTGd
language:
C++ (gcc 8.3)
created:
13 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!