UVa 760 - DNA Sequencing

#include <iostream>
#include <map>
#include <stack>
#include <stddef.h>
#include <string>
#include <vector>
using namespace std;

class TrieNode {
public:
	bool suffixEnd;
	map<char, TrieNode*> children;

	TrieNode() {
		suffixEnd = false;
	}

	TrieNode* getChild(char ch) {
		return children[ch];
	}
	TrieNode* newChild(char ch) {
		return children[ch] = new TrieNode;
	}
};

class Trie {
public:
	TrieNode* root;
	Trie() {
		root = new TrieNode;
	}
	void insertSuffixes(string word) {
		int len = word.length();
		for (int i = 0; i < len; i++) {
			TrieNode* node = root;
			for (int j = i; j < len; j++) {
				char ch = word[j];
				if (node->getChild(ch) != NULL)
					node = node->getChild(ch);
				else
					node = node->newChild(ch);
			}
			node->suffixEnd = true;
		}
	}
};

// Finds longest common substring between two given strings
// end1 and end2 must not be contained in the text, change values accordingly
class LongestCommonSubstrings {
private:
	const static char end1 = '!';
	const static char end2 = '@';
	static pair<bool, bool> findRecursive(TrieNode* node, deque<char> & path_to_root, int depth, vector<string> & substrings, int & longest_found) {
		int children_count = 0;
		bool subtreeHasEnd1 = false, subtreeHasEnd2 = false;

		for (map<char, TrieNode*>::iterator I = node->children.begin(); I != node->children.end(); I++) {
			children_count++;
			path_to_root.push_back(I->first);

			pair<bool, bool> hasEnds = findRecursive(I->second, path_to_root, depth + 1, substrings, longest_found);

			subtreeHasEnd1 = subtreeHasEnd1 || I->first == end1 || hasEnds.first;
			subtreeHasEnd2 = subtreeHasEnd2 || I->first == end2 || hasEnds.second;
			path_to_root.pop_back();
		}

		if ((children_count >= 2 || (children_count == 1 && node->suffixEnd)) && (subtreeHasEnd1 && subtreeHasEnd2)) {
			if (depth > longest_found) {
				substrings.clear();
				substrings.push_back(string(path_to_root.begin(), path_to_root.end()));
				longest_found = depth;
			} else if (depth == longest_found) {
				substrings.push_back(string(path_to_root.begin(), path_to_root.end()));
			}
		}

		return make_pair(subtreeHasEnd1, subtreeHasEnd2);
	}
public:
	static vector<string> findAll(const string & word1, const string & word2) {
		Trie trie = Trie();
		trie.insertSuffixes(word1 + end1);
		trie.insertSuffixes(word2 + end2);
		vector<string> substrings;
		deque<char> path_to_root;
		int longest_found = 0;
		findRecursive(trie.root, path_to_root, 0, substrings, longest_found);
		return substrings;
	}
};

int main() {

	string a, b, c;
	int cases = 0;
	while (true) {
		cases++;
		if (cases > 1)
			getline(cin, c);

		if (getline(cin, a)) {
			getline(cin, b);
		} else
			break;

		if (cases > 1)
			cout << endl;

		vector<string> sol = LongestCommonSubstrings::findAll(a, b);
		if (sol.empty() || (sol.size() == 1 && sol[0].length() == 0))
			cout << "No common sequence." << endl;
		else
			for (int i = 0; i < sol.size(); i++)
				cout << sol[i] << endl;
	}

	return 0;
}