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; }