Node.hpp

#pragma once

#include <memory>
#include <unordered_map>

static const int ALPHABETSIZE = 26;

struct Node {
	bool isEnd;
	int prefixCount;
	std::unordered_map<char, std::shared_ptr<Node>> children;
};

source.cpp

#include <iostream>
#include <fstream>
#include <algorithm>
#include "Trie.hpp"

int main() {
	Trie trie;
	std::ifstream file;
	std::string word, input;

	file.open("dictionary.txt");

	//Ask for input
	std::cin >> input;

	char lowInput = tolower(input[0]);

	auto beenHere = false;
	//Add every word to the trie.
	while (std::getline(file, word)) {
		char lowWord = tolower(word[0]);
		//if word's first character equals to input's, go on, else, dont add it onto the trie.
		if (lowWord == lowInput) {
			beenHere = true;
			trie.insert(word);
			//if a perfect match has been found, break out of the loop.
			if (word == input) break;
		}
		//If you've already been on the word's first character
		//, and it isn't the same as the input's you are done.
		if (beenHere && lowWord != lowInput) break;
	}

	auto errors = false;
	std::string x = "";
	for (const char& i : input) {
		x += i;
		if (trie.wordsWithPrefix(x) == 0) {
			errors = true;
			std::cout << x << "<" << input.substr(x.length());
			break;
		}
	}
	if (!errors)
		std::cout << "There are no errors.";
}

Trie.cpp

#include "Trie.hpp"

Trie::Trie() : head(std::make_shared<Node>()){
	head->isEnd = false;
	head->prefixCount = 0;
}

std::shared_ptr<Node> Trie::atPrefix(const std::string& prefix) const{
	auto current = head;
	for (const char& c : prefix) {
		auto letter = c - 'a';
		auto next = current->children[letter];
		if (!next) return nullptr;
		current = next;
	}
	return current;
}

void Trie::insert(const std::string& word) const{
	auto current = head;
	for (const char& c : word) {
		auto letter = c - 'a';
		auto& next = current->children[letter];
		if (!next) next = std::make_shared<Node>();
		current->children[letter]->prefixCount++;
		current = current->children[letter];
	}

	current->isEnd = true;
}

bool Trie::search(const std::string& word) const{
	auto node = atPrefix(word);
	return node && node->isEnd;
}

unsigned int Trie::wordsWithPrefix(const std::string& prefix) const {
	auto node = atPrefix(prefix);
	return node ? node->prefixCount : 0;
}

Trie.hpp

#pragma once

#include "Node.hpp"
#include <string>

class Trie {
	std::shared_ptr<Node> head;

	std::shared_ptr<Node> atPrefix(const std::string& prefix) const;
public:
	Trie();

	void insert(const std::string& word) const;
	bool search(const std::string& word) const;

	unsigned int wordsWithPrefix(const std::string& prefix) const;
};