#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <iterator>
#include <algorithm>

unsigned BinarySearch(std::wstring& str, unsigned left, unsigned right, wchar_t tgt)
{
	if (left > right)
		return 0;
	int ctr = left + (right - left) / 2;
	if (tgt < str[ctr])
		return BinarySearch(str, left, ctr - 1, tgt);
	else if (tgt > str[ctr])
		return BinarySearch(str, ctr + 1, right, tgt);
	else
	{
		int count = 1;
		if (ctr != right)
			for (int t = ctr + 1; t <= right && str[t] == tgt; count++, t++);
		if (ctr != left)
			for (int t = ctr - 1; t >= left && str[t] == tgt; count++, t--);
		return count;
	}
}

int main()
{
	std::wcin.imbue(std::locale("rus_rus.866"));
	std::wcout.imbue(std::locale("rus_rus.866"));
	std::wstring buffer;
	std::vector<std::wstring> words;
	for (;;)
	{
		std::wcout << L"Введите текст. Для прекращения введите пустую строку:" << std::endl;
		do
		{
			std::getline(std::wcin, buffer);
			std::wistringstream iss(buffer);
			std::copy(std::istream_iterator<std::wstring, wchar_t>(iss),
				std::istream_iterator<std::wstring, wchar_t>(),
				std::back_inserter(words));
		} while (!buffer.empty());
		if (words.empty())
		{
			std::wcout << L"Вы не ввели ни одного слова. Попробуйте снова" << std::endl;
			continue;
		}
		break;
	}
	for (;;)
	{
		std::wcout << L"Введите маску слова в формате \"st*d**t\" (student) :" << std::endl;
		std::getline(std::wcin, buffer);
		if (buffer.empty())
		{
			std::wcout << L"Вы ввели пустую строку. Попробуйте снова" << std::endl;
			continue;
		}
		break;
	}


	bool have = false;
	for (auto& word : words)
		if (word.length() == buffer.length())
		{
			bool flag = true;
			for (auto i = 0; i < word.length(); ++i)
				if (buffer[i] != L'*' && word[i] != buffer[i])
				{
					flag = false;
					break;
				}
			if (flag)
			{
				if (!have)
				{
					std::wcout << L"Совпадения: " << std::endl;
					have = true;
				}
				std::wcout << word << std::endl;
			}
		}
	if (!have)
		std::wcout << L"Совпадений нет" << std::endl;
	std::wcout << std::endl;
	for (;;)
	{
		std::wcout << L"Введите строку, в которой будет производиться бинарный поиск:" << std::endl;
		std::getline(std::wcin, buffer);
		if (buffer.empty())
		{
			std::wcout << L"Вы ввели пустую строку. Попробуйте снова" << std::endl;
			continue;
		}
		break;
	}
	std::wcout << L"Введите искомую букву:" << std::endl;
	wchar_t target;
	std::wcin >> target;
	std::sort(buffer.begin(), buffer.end());
	std::wcout << L"Найдено: " << BinarySearch(buffer, 0, buffer.length() - 1, target) << std::endl;
	system("pause");
	return 0;
}