#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_LEVENSHTEIN_DISTANCE_STRING
#define CA_UWATERLOO_ALUMNI_DWHARDER_LEVENSHTEIN_DISTANCE_STRING

#include <string>

namespace String_distances {
	namespace 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 table[t.length()];

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

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

							table[j] = min( 
								table[j - 1] + 1,
								tmp + subs,
								table[j] + 1
							);

							tmp = tmp1;
						}
					}

					return table[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;
					}
				}
		};
	}
}

#endif