UVa 508

Morse Mismatches.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <regex>
#include <string>
#include <vector>

using namespace std;

map<char, string> m_characterToMorseMappingTable;
map<string, string> m_contextMorseWordsMappingTable;
map<string, bool> m_isMorseRepeated;

vector<string> splitSpaces(const string &targetString)
{
	regex pattern(" ");
	auto splitContents = vector<string> {};
	copy_if(sregex_token_iterator(targetString.begin(), targetString.end(), pattern, -1), sregex_token_iterator(), back_inserter(splitContents),
		[](const string &data) { return !data.empty(); });
	return splitContents;
}

void createCharacterMappingTable(const vector<string> &mappingStringList)
{
	m_characterToMorseMappingTable.clear();
	for (const auto &mappingString: mappingStringList)
	{
		auto splitContents = splitSpaces(mappingString);
		if (!splitContents.empty())
		{
			auto character = splitContents[0].at(0);
			auto morseWords = accumulate(splitContents.begin() + 1, splitContents.end(), string {});
			m_characterToMorseMappingTable[character] = morseWords;
		}
	}
}

void createContextTable(vector<string> &contextStringList)
{
	m_isMorseRepeated.clear();
	m_contextMorseWordsMappingTable.clear();

	sort(contextStringList.begin(), contextStringList.end(), 
	     [](const string &s1, const string &s2) { return strcmp(s1.c_str(), s2.c_str()) == -1; });

	for (const auto &contextString: contextStringList)
	{
		auto morseWords = accumulate(contextString.begin(), contextString.end(), string {}, 
					     [&](string &baseString, const char &c) { return baseString + m_characterToMorseMappingTable[c]; });
		if (morseWords.empty())
		{
			continue;
		}

		m_isMorseRepeated[morseWords] = m_isMorseRepeated.count(morseWords);
		if (!m_isMorseRepeated[morseWords])
		{
			m_contextMorseWordsMappingTable[contextString] = morseWords;
		}
	}
}

vector<string> createMorseWordsQuery(const vector<string> &contentStringList)
{
	auto contentList = vector<string> {};
	for (const auto &contentString: contentStringList)
	{
		auto splitContentList = splitSpaces(contentString);
		copy(splitContentList.begin(), splitContentList.end(), back_inserter(contentList));
	}
	return contentList;
}

int calculateMaxPrefixMorseNumber(const string &morseWords, const string &morseContent)
{
	auto currentIndex = 0;
	auto sameCharacterNumber = 0;
	while (currentIndex < morseWords.size() && currentIndex < morseContent.size())
	{
		if (morseWords[currentIndex] != morseContent[currentIndex])
		{
			break;
		}

		sameCharacterNumber++;
		currentIndex++;
	}
	return sameCharacterNumber;
}

int getRedundantNumber(int length1, int length2, int matchedNumber)
{
	if (length1 == matchedNumber)
	{
		return length2 - matchedNumber;
	}
	else if (length2 == matchedNumber)
	{
		return length1 - matchedNumber;
	}
	return numeric_limits<int>::max();
}

string findMostClosestContext(const string &morseWordsQuery)
{
	auto minRedundantNumber = numeric_limits<int>::max();
	auto paritalMatchedContextWords = m_contextMorseWordsMappingTable.begin()->first;
	for (const auto &mappingPair: m_contextMorseWordsMappingTable)
	{
		auto contextWords = mappingPair.first;
		auto morseWords = mappingPair.second;

		auto matchedNumber = calculateMaxPrefixMorseNumber(morseWords, morseWordsQuery);
		auto redundantNumber = getRedundantNumber(morseWordsQuery.size(), morseWords.size(), matchedNumber);
		if (minRedundantNumber > redundantNumber)
		{
			minRedundantNumber = redundantNumber;
			paritalMatchedContextWords = contextWords;
		}
	}
	return paritalMatchedContextWords;
}

void solve(const vector<string> &contentStringList)
{
	auto morseWordsQueryList = createMorseWordsQuery(contentStringList);
	for (const auto &morseWordsQuery: morseWordsQueryList)
	{
		auto postFixWords = string {"?"};
		auto closestContextWords = findMostClosestContext(morseWordsQuery);
		if (m_contextMorseWordsMappingTable[closestContextWords] == morseWordsQuery)
		{
			postFixWords = m_isMorseRepeated[morseWordsQuery] ? "!" : "";
		}
		cout << closestContextWords + postFixWords << endl;
	}
}

vector<string> inputMultiLineData()
{
	auto inputString = string {};
	auto multiLineStringList = vector<string> {};
	while (getline(cin, inputString))
	{
		if (inputString.find('*') != string::npos)
		{
			break;
		}
		multiLineStringList.push_back(inputString);
	}
	return multiLineStringList;
}

int main()
{
	auto morseMappingList = inputMultiLineData();
	auto contextWordsList = inputMultiLineData();
	auto contentStringList = inputMultiLineData();

	createCharacterMappingTable(morseMappingList);
	createContextTable(contextWordsList);
	solve(contentStringList);

	return 0;
}