#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_DAMERAU_LEVENSHTEIN_DISTANCE_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_DAMERAU_LEVENSHTEIN_DISTANCE_BASIC

#include <string>

namespace String_distances {
	namespace Damerau_Levenshtein_distance {
		class Basic {
			public:
				static
				int distance( std::string const &s, std::string const &t ) {
					int table[s.length() + 1][t.length() + 1];

					for ( int i = 0; i <= s.length(); ++i ) {
						table[i][0] = i;
					}
					
					for ( int j = 1; j <= t.length(); ++j ) {
						table[0][j] = j;
					}

					for ( int i = 1; i <= s.length(); ++i ) {
						for ( int j = 1; j <= t.length(); ++j ) {
							int subs = ( s[i - 1] != t[j - 1] ) ? 1 : 0;
							
							table[i][j] = min( 
								table[i - 1][  j  ] + 1,
								table[i - 1][j - 1] + subs,
								table[  i  ][j - 1] + 1
							);

							if ( i > 1 && j > 1 && s[i - 1] != t[j - 1] && s[i - 1] == t[j - 2] && s[i - 2] == t[j - 1] ) {
						               table[i][j] = std::min( table[i][j], table[i - 2][j - 2] + 1 );
							}
						}
					}

					return table[s.length()][t.length()];
				}

			private:
				static
				int min( int a, int b, int c ) {
					return std::min( std::min( a, b ), c );
				}
		};
	}
}

#endif