#ifndef PREFIX_H
#define PREFIX_H
#include <iostream>
#include <cstdlib>  //for the functions srand and rand
#include <string>   //for class string
#include <queue>    //for class queue
#include <map>      //for class map
#include <ctime>    //for the function time
using namespace std;

class prefix {
private:
	queue<string> phrase;        //the words that constitute the prefix
	static const int npref;      //how many words in a prefix
	static const string dummy;   //dummy word, different from every word of real input
	static map<prefix, vector<string> > m;
public:
	prefix() {
		//Fill the newborn prefix with dummy words.
		for (int i {0}; i < npref; ++i) {
			add(dummy);
		}
	}

	void read_input() {
		for (string s; cin >> s;) { //Read all the input words.
			add(s);
		}

		add(dummy);   //Add a dummy word to mark the end of the input.
	}

	void add(const string& word) {
		//If this prefix is already full, add this word to the
		//vector of the prefix's suffixes.
		if (phrase.size() == npref) {
			vector<string>& suffix {m[*this]};
			suffix.push_back(word);
		}
		advance(word);
	}

	void generate_output() {
		srand(time(nullptr));   //Seed the random number generator.
	
		for (int i {0}; i < 10000; ++i) {   //At most 10000 words
			const vector<string>& suffix {m[*this]};
			const auto r {rand() % suffix.size()};  //a random subscript
			const string& word {suffix[r]};
			if (word == dummy) {
				break;
			}
			cout << word << "\n";
			advance(word);
		}
	}

	void advance(const string& word) {
		if (phrase.size() == npref) {
			phrase.pop();  //make rooom for the next word
		}
		phrase.push(word);
	}

	//To allow us to store prefixes in a map.
	friend bool operator<(const prefix& p1, const prefix& p2) {
		return p1.phrase < p2.phrase;
	}
};

#endif