fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3.  
  4. using namespace std;
  5.  
  6. int DamerauLevenshtein(char[], char[], int, int);
  7.  
  8. int main()
  9. {
  10.     char A[200000], B[200000];
  11.     cout<< "Input 1: ";
  12.     cin>>A;
  13.     cout<<"Input 2: ";
  14.     cin>>B;
  15.  
  16.     cout<<"Damerau Levenshtein distance: "<<DamerauLevenshtein(A,B,strlen(A),strlen(B));
  17.     return 0;
  18. }
  19.  
  20.  
  21. int DamerauLevenshtein(char A[200000], char B[200000], int m, int n)
  22. {
  23.     int table[m+1][n+1];
  24.  
  25.     int cost;
  26.     int counter=0;
  27.  
  28.     for(int i=0; i<=m; i++)
  29.     {
  30.     	for(int j=0; j<=n; j++)
  31.     	{
  32.     		table[i][j]=0;
  33.     	}
  34.     }
  35.     for(int i=0; i<=m; i++)
  36.     {
  37.         table[i][0]= i;
  38.     }
  39.     for(int j=0; j<=n; j++)
  40.     {
  41.         table[0][j]= j;
  42.     }
  43.  
  44.     for(int j=1; j<=n; j++)
  45.     {
  46.         for(int i=1; i<=m; i++)
  47.         {
  48.             counter++;
  49.  
  50.             if(A[i-1]==B[j-1])
  51.             {
  52.                 cost=0;
  53.             }
  54.             else
  55.             {
  56.                 cost=1;
  57.             }
  58.  
  59.             int minimum, deletion, substitution, insertion;
  60.  
  61.             deletion= table[i-1][j]+1;
  62.             insertion= table[i][j-1]+1;
  63.             substitution= table[i-1][j-1]+cost;
  64.  
  65.             minimum= deletion;
  66.             if(insertion<minimum)
  67.             {
  68.                 minimum= insertion;
  69.             }
  70.             else if(substitution<minimum)
  71.             {
  72.                 minimum= substitution;
  73.             }
  74.  
  75.             table[i][j]= minimum;
  76.  
  77.             if((i>1 and j>1))
  78.             {
  79.             	if((A[i-1]==B[j-2]) and (A[i-2]==B[j-1]))
  80.             {
  81.  
  82.                 int transposition= table[i-2][j-2]+cost;
  83.  
  84.                 if(table[i][j]>transposition)
  85.                 {
  86.                     table[i][j]= transposition;
  87.                 }
  88.             }
  89.             }
  90.         }
  91.     }
  92.         for (int i=0; i<=m; i++)
  93.         {
  94.         	for (int j=0; j<=n; j++)
  95.              {
  96.              	cout<<table[i][j];
  97.              }
  98.              cout<<endl;
  99.         }
  100.  
  101.  
  102.     cout<<"Number of iteration: "<<counter<<endl;
  103.  
  104.     return table[m][n];
  105.  
  106. }
  107.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
apcat
apabct
stdout
copy 
Input 1: Input 2: Damerau Levenshtein distance: 0123456
1012345
2101234
3211234
4321234
5432234
Number of iteration: 30
4
https://ideone.com/g9557l
language:
C++ (gcc 8.3)
created:
5 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!