#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sys/time.h>
#include <unistd.h>
 
#define microsec 1000000.0
using namespace std;
 
vector <int> startPos;
vector <int> endPos;
 
class TimeTracker {
 private:
  struct timeval start_time;
  struct timeval stop_time;
  bool  running;
 public:
  TimeTracker() {
    running=false;
  }
 
  void Start() {
 gettimeofday(&start_time, (struct timezone *)0);
    running=true;
  }
 
  double Stop() {
    double st, en;
    if (!running) return(-1.0);
    else {
      gettimeofday(&stop_time, (struct timezone *)0);
      st = start_time.tv_sec + (start_time.tv_usec/microsec);
      en = stop_time.tv_sec + (stop_time.tv_usec/microsec);
      running=false;
      return (double)((en - st));
    }
  }
};
 
struct SuffNode // declare a new struct
{
	string pre;
	vector <SuffNode> suff;
	vector <int> pos;
};
 
string toString(string level, SuffNode* suffix)			//return the output string
	{
	    string tree = level + suffix->pre;
		tree += "\n";
		if(suffix->suff.size() != 0)
		{
			int c = suffix->suff.size();
			level += "-";
			for(int i = 0; i < c; i++)
			{
				SuffNode aSuff = suffix->suff.at(i);
				tree += toString(level, &aSuff);
			}
		}
		return tree;
	}
 
	vector<SuffNode> put(string key, vector <SuffNode>& tree, int poss)			//method for creating suffix tree by put each suffix one by one
	{
		if(tree.size() == 0)         //put first suffix
		{
			SuffNode node;
			node.pre = key;
			node.pos.push_back(poss);
			tree.push_back( node);
		}
		else								//put subsequent suffix
		{
			int tsize = tree.size();				//size of arraylist
			int i = 0;
			bool check = true;
 
			while( i < tsize && check)		//if it already has list keep checking the suffix with the string in each node
			{
				string test = tree[i].pre;							//get string in that node
				vector <int> poslist;
				poslist.assign(tree[i].pos.begin(), tree[i].pos.end());
				int keysize = key.length();								//get size of input suffix
				int testsize = test.length();								//get size of string in the node
				int j = 1;
				bool c = true;
 
				if(test[0] == key[0])						//if first character of suffix match with the first character of string in the node
				{
					while( j < keysize && j < testsize && c)			//keep checking the matching
					{
						if(test[j] == key[j])				//if next character match
						{
							j++;														//go to next character
						}
						else															//out of while loop
						{
							c = false;
						}
					}//end inner while
					string newPre = test.substr(0, j);				//get new string to put in current node
					tree[i].pre = newPre;							//add new string
 
					if(!c)																//if match only some part of the string
					{
						string newS1 = test.substr(j);	
						string newS2 = key.substr(j);	
						if(tree[i].suff.size() == 0)						//if there are no list in the node
						{
							SuffNode node1;		//create new object(node)
							node1.pre = newS1;						//add string into new node
							node1.pos.assign(poslist.begin(), poslist.end());
							tree[i].suff.push_back(node1);							//add new node into the arraylist
							SuffNode node2;		//create new object(node)
							node2.pre = newS2;					//add string into new node
							node2.pos.push_back(poss);						//add new position into position list in this node
							tree[i].suff.push_back(node2);							//add new node into the arraylist
						}
						else															//if it already has list
						{
							SuffNode node11;	//create new object(node)
							node11.pre = newS1;					//add string (new string of current node) into new node 
							node11.suff.assign(tree[i].suff.begin(), tree[i].suff.end());
							node11.pos.assign(poslist.begin(), poslist.end());
							tree[i].suff.clear();									//clear list of current node
							tree[i].suff.push_back(node11);						//add new list to current node
							SuffNode node12;	//create new object(node)
							node12.pre = newS2;					//add string (new string of input suffix) into new node 
							node12.pos.push_back(poss);						//add new position into the position list int this node
							tree[i].suff.push_back(node12);						//add new node into the current list
						}
					} //end if !c
					else																//if every character in the test stirng match
					{
						string newString = key.substr(j);			//get new string of input suffix
 
						if(tree[i].suff.size() == 0)						//if no list in current node
						{
							SuffNode nnode;		//create new node
							nnode.pre = newString;				//add string into new node
							nnode.pos.push_back(poss);						//add new position into the position list
							tree[i].suff.push_back(nnode);							//input new node into current list
						}
						else															//if it already has the list
						{
							vector <SuffNode> newL = put(newString, tree[i].suff, poss);		//put new input suffix into the current tree(current list)
							tree[i].suff.assign(newL.begin(), newL.end());
						}
					}//end else !c
					tree[i].pos.push_back(poss);								//add new position
					check = false;
				}//end if first character match
				else		// if first character not match go to next index of arraylist
				{
					i++;
				}
			}//end outer while 
 
			if(i >= tsize)     //no match in arraylist
			{
				SuffNode nNode;	//create new node
				nNode.pre = key;							//add input suffix into new node
				nNode.pos.push_back(poss);                     //add position into new node
				tree.push_back(nNode);								//add new node into current list
			}
		}//end else
 
		return tree;
	}
 
 
bool matching(vector<SuffNode> tree, string s, int count)		//method for find the match substring in arraylist
	{
		bool match = false;
		int sSize = s.length();
		int listSize = tree.size();
		int i = 0;
		bool check = true;
		while( i < listSize && check)									//keep checking each string in each node until know whether match or not match
		{
			string test = tree[i].pre;							//get string in that node
			int testsize = test.length();
			int j = 1;
			bool c = true;
			if(test[0] == s[0])						//if first character of string match with the first character of string in the node
			{
				if(count == 0)
				{
					startPos = tree[i].pos;		//get position from the node that the first character matched
				}
				while( j < sSize && j < testsize && c)			//keep checking the matching
				{
					if(test[j] == s[j])				//if next character match
					{
						j++;														//go to next character
					}
					else															//out of while loop
					{
						c = false;
					}
				}//end inner while
 
				if(!c && j == sSize)											//if all characters match
				{
					match = true;
					endPos = tree[i].pos;
				}
				else if(!c)														//if either one characters not match
				{
					match = false;
				}
				else if (j == sSize)											//if all character match
				{
					match = true;
					endPos = tree[i].pos;		//get position from the node that the last character matched
				}
				else if (j < sSize)											//if match the string in the node but still have character left in the input string
				{
					string newString = s.substr(j);				//get the string have left
					count++;
					match = matching(tree[i].suff, newString, count);		//continue finding the match
				}
				check = false;
			} //end if match
			else
			{
				i++;
			} //end if first character not match			
		} //end while
 
		if(i >= listSize)     //no match in arraylist
		{
			match = false;
		}
		return match;
	}
 
 
main()
{
	string line, filename;
	putname:
	cout << "Please input file name: ";
	getline (cin, filename);
 
	char *name = new char[filename.length()+1];
 
    strcpy ( name, filename.c_str() ); // that is correct
 
 
	ifstream myfile (name);
	if (myfile.is_open())
	{
		getline (myfile,line);
		myfile.close();
	}
	else 
	{
		cout << "Unable to open file\n"; 
		goto putname;
	}
 
	line += "$";
	cout << line << endl;
	Tree t;
	TimeTracker tt;
	tt.Start();
	vector <SuffNode> suftree;
	for (int i = line.length(); i > 0; i--)					//put each suffix of input string into class tree to create suffix tree
	{
		suftree = put(line.substr(i-1),suftree,(i-1));	
	}
	cout << "Build Done! Time taken = " << tt.Stop() << " seconds.\n" << endl;
	string tree = "";
	for (int j = 0; j < suftree.size(); j++ )				//get created suffix tree and keep in form of string for presentation
	{
		tree += toString("-", &suftree[j]);
	}
	cout << tree;
	string ans;
	cout << "\nNeed to search (y/n) : ";
	getline(cin, ans);
	if ( ans == "y")
	{
		string search, files;
		putname2:
		cout << "Please input file name: ";
		getline (cin, files);
 
		char *names = new char[files.length()+1];
		strcpy ( names, files.c_str() ); // that is correct
		ifstream myfiles (names);
		if (myfiles.is_open())
		{
			getline (myfiles,search);
			myfiles.close();
			TimeTracker ts;
			ts.Start();
			bool match = matching(suftree,search,0);
			cout << "Searching Done! Time taken = " << ts.Stop() << " seconds." << endl;
 
			if(match)														//if searched string match														
					{	
						cout << "\nMATCH!!!" << endl;
						vector<int> posi;
						int sSize = startPos.size();
						int eSize = endPos.size();
 
						for(int k = 0; k < eSize; k++)
						{
							int epoint =  endPos[k];
							for(int m = 0; m < sSize; m++)
							{
								int spoint = startPos[m];
								if(epoint == spoint)
								{
									posi.push_back(spoint);
								}
							}//end inner for loop
						}//end outer for loop
						int length = search.length() - 1;
						int numMatch = posi.size();
						cout <<  "Number of Matching : " << numMatch  << "\n\n";
						for(int p = numMatch-1; p >= 0; p--)
						{
							int stat = posi[p];
							int en = stat + length;
							cout << "position : ( " << stat << ","  << en  << " )\n";
						}
 
					}//end if match
					else
					{
						cout << "\nNOT MATCH!!!" << endl;
					}//end else (not match)	
 
		}
 
		else 
		{
			cout << "Unable to open file\n"; 
			goto putname2;
		}
 
	}
getchar(); 
 
}