Previously, I had looked at calculating the Levenshtein distance between two strings. In that post I did some hand waving and claimed that the dynamic implementation will not register with the time command. Well I decided to test that claim and here is the proof.

#include <iostream>
#include <string>
using namespace std;
int minimum(int d, int i, int s);

int main(){
 string s, t;
 cin >> s >> t;
 int sl = s.length()+1;
 int tl = t.length()+1;
 int* previous = new int[sl];
 int* current = new int[sl];
 //initialize current
 for(int j=0; j<sl; ++j) *(current+j) = j;
 for(int j=1; j<tl; ++j){
  //Swap current and previous
  int* tmp = previous;
  previous = current;
  current = tmp;
  *(current) = j;
  for(int k=1; k<sl; ++k){
   if(s.at(k-1) == t.at(j-1)) *(current+k) = *(previous+k-1);
   else{
    *(current+k) = minimum(*(previous+k),*(current+k-1),*(previous+k-1))+1;
   }
  }
 }
 cout << *(current+sl-1) << endl;
 return 0;
}

int minimum(int d, int i, int s){
 int min = d;
 if(i < min) min = i;
 if(s < min) min = s;
 return min;
}