#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_DAMERAU_LEVENSHTEIN_DISTANCE_STRING
#define CA_UWATERLOO_ALUMNI_DWHARDER_DAMERAU_LEVENSHTEIN_DISTANCE_STRING

#include <string>

namespace String_distances {
	namespace Damerau_Levenshtein_distance {
		class String {
			public:
				static
				int distance( std::string const &s, std::string const &t ) {
					if ( t.length() > s.length() ) {
						return distance( t, s );
					}

					int column0[t.length()];
					int column1[t.length()];
					int column2[t.length()];

					for ( int j = 0; j <= t.length(); ++j ) {
						column2[j] = j;
					}

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

						column1[j] = min( 
							column1[j - 1] + 1,
							column2[j - 1] + subs,
							column2[j] + 1
						);
					}

					for ( int i = 2; i <= s.length(); ++i ) {
						column0[0] = i;

						int subs = ( s[i - 1] != t[0] ) ? 1 : 0;

						column0[1] = min(
							column0[0] + 1,
							column1[0] + subs,
							column1[1] + 1
						);

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

							if ( s[i - 1] == t[j - 2] && s[i - 2] == t[j - 1] ) {
								column0[j] = min( 
									column0[j - 1] + 1,
									column1[j - 1] + subs,
									column1[j] + 1,
									column2[j - 2] + subs
								);
							} else {
								column0[j] = min( 
									column0[j - 1] + 1,
									column1[j - 1] + subs,
									column1[j] + 1
								);
							}
						}

						for ( int j = 0; j <= t.length(); ++j ) {
							column2[j] = column1[j];
							column1[j] = column0[j];
						}
					}

					return column0[t.length()];
				}

			private:
				inline static
				int min( int a, int b, int c ) {
					if ( a < b ) {
						return ( a < c ) ? a : c;
					} else {
						return ( b < c ) ? b : c;
					}
				}

				inline static
				int min( int a, int b, int c, int d ) {
					if ( a < b ) {
						if ( a < c ) {
							return ( a < d ) ? a : d;
						} else {
							return ( c < d ) ? c : d;
						}
					} else {
						if ( b < c ) {
							return ( b < d ) ? b : d;
						} else {
							return ( c < d ) ? c : d;
						}
					}
				}
		};
	}
}

#endif