#include <locale.h>
#include <Windows.h>
#include <iostream>
#include <limits>

template<class _Ty>
class Timer
	{
public:
	LARGE_INTEGER str, fre, fin;
	
	inline void start()
		{
		QueryPerformanceFrequency(&fre);
		QueryPerformanceCounter(&str);
		}

	inline void finish()
		{
		QueryPerformanceCounter(&fin);
		}
	
	inline _Ty operator*()
		{
		return (_Ty)(_Ty(fin.QuadPart - str.QuadPart) * 10e9 / _Ty(fre.QuadPart));
		}

	inline void out()
		{
		std::cout.precision(std::numeric_limits<long double>::digits10);
		std::cout << **this << "ns" << std::endl;
		}

	inline void outms()
		{
		std::cout.precision(std::numeric_limits<long double>::digits10);
		std::cout << (_Ty)(_Ty(fin.QuadPart - str.QuadPart) * 10e3 / _Ty(fre.QuadPart)) << "ms" << std::endl;
		}
	
	inline void outs()
		{
		std::cout.precision(std::numeric_limits<long double>::digits10);
		std::cout << (_Ty)(_Ty(fin.QuadPart - str.QuadPart) / _Ty(fre.QuadPart)) << "ms" << std::endl;
		}

	};
	
	class WString final
	{
		wchar_t *m_ptr;
		wchar_t *m_last;
		size_t   m_length;

		bool srp = false;

	public:

		static const size_t error = -1;

		WString()
			: m_length(0)
			, m_ptr(nullptr)
			, m_last(m_ptr)
		{
		}
		
		WString(const wchar_t *ptr)
		{
			InitString(ptr);
		}
		void InitString(const wchar_t *str)
		{
			m_length = wcslen(str);
			m_ptr = new wchar_t[m_length + 1];
			m_last = m_ptr + m_length - 1;
			wcsncpy_s(m_ptr, m_length + 1, str, m_length);
		}
		
		typedef unsigned long long  i64u;

		static inline  i64u    has_zero_wide(const i64u n)
		{
			const   i64u    finder = 0x0001000100010001ULL;
			const   i64u    masker = 0x8000800080008000ULL;
			return  (n - finder) & (~n & masker);
		}

		static inline  i64u    has_some_wide(const wchar_t* s, const i64u cs)
		{
			return  has_zero_wide(*(i64u *)s ^ cs);
		}

		static wchar_t*        wcsrnchr(const wchar_t* haystack, size_t len, wchar_t needle)
		{
			const   i64u cs = ((i64u)needle << 48) | ((i64u)needle << 32) | ((i64u)needle << 16) | needle;

			if (has_some_wide(haystack + len - 4, cs))
			{
				if (haystack[len - 1] == needle) return  (wchar_t*)haystack + len - 1;
				if (haystack[len - 2] == needle) return  (wchar_t*)haystack + len - 2;
				if (haystack[len - 3] == needle) return  (wchar_t*)haystack + len - 3;
				return (wchar_t*)haystack + len - 4;
			}

			wchar_t*    hay;

			for (hay = (wchar_t*)((i64u)(haystack + len - 1) & -8LL); hay >= haystack; hay -= 4)
				if (has_some_wide(hay, cs))
				{
					if (hay[0] == needle)  return  hay;
					if (hay[1] == needle)  return  hay + 1;
					if (hay[2] == needle)  return  (wchar_t*)hay + 2;
					return  hay + 3;
				}

			for (hay += 3; hay >= haystack; --hay)
				if (*hay == needle)  return  hay;

			return NULL;
		}

		size_t FindLastHelper(const wchar_t *str, size_t ends, size_t len) const
		{
			if (ends >= m_length)
				throw(new StringException(StringErrorCode::ComparasionSizeException));
			
			size_t  searchLen = m_length - ends;
			wchar_t frontch = str[len - 1];
			wchar_t *last = m_last - ends;
			wchar_t *ptr = m_ptr; /* const */

			do
			{
				wchar_t backup = *last;
				*last = 0;

				if ( (ptr = wcsrnchr(m_ptr, searchLen, frontch)) == NULL )
				//if ( (ptr = wcsrchr(m_ptr, frontch)) == NULL )
					break;
				else if ( !wcscmp(ptr - len, str) )
				{
					*last = backup;
					return ptr - m_ptr - 1;
				}

				*last = backup;
				last = ptr;
			} while (true);
			
			return error;
		}
		
		size_t FindLast(const wchar_t *str, size_t ends) const
		{
			return FindLastHelper(str, ends, wcslen(str));
		}

		size_t FindLast(const WString& refer, size_t ends) const
		{
			return FindLastHelper(refer.m_ptr, ends, refer.m_length);
		}
		
		size_t FindLast(const wchar_t *str) const
		{
			return FindLastHelper(str, 0, wcslen(str));
		}
		
		size_t FindLast(const WString& refer) const
		{
			return FindLastHelper(refer.m_ptr, 0, refer.m_length);
		}
	};
	
void testfind()
{
#define L1(x)   x x x x
#define L2(x)   L1(x) L1(x) L1(x) L1(x)
#define L3(x)	L2(x) L2(x) L2(x) L2(x)
#define L4(x)	L3(x) L3(x) L3(x) L3(x)
#define L5(x)	L4(x) L4(x) L4(x) L4(x)
#define L6(x)	L5(x) L5(x) L5(x) L5(x)
#define L7(x)	L6(x) L6(x) L6(x) L6(x)
	WString testTarget(L"rokomo" L6(L"koromo"));
	WString findWhat(L"rokomo");

	Timer<long double> timer;
	timer.start();
	size_t pos = testTarget.FindLast(findWhat);
	timer.finish();

	std::cout << pos << std::endl;
	timer.outms();
}


int _tmain()
{
	_wsetlocale(LC_ALL, L"korean");

	std::locale::global(std::locale("kor"));
	std::wcout.imbue(std::locale("kor"));
	std::wcin.imbue(std::locale("kor"));

	testfind();

	return 0;
}