#pragma warning(disable:4996)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<fstream>

#define inf 100000000
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

#define Tabu_prob 1				    // rejects tabu listed substrings with "tabu_prob" probability
#define Distinct_Substr 300005		// Maximum no. of distinct substrings
#define NO_UPDATE 70			// No update for NO_UPDATE iterations -> terminate
#define MAX_RUN 4				
#define POPULATION_SIZE (n*2)		// No. of ants = some multiple of no. of target strings in the input
#define T 305						// Maximum Cardinality of the set of target string
#define M 305						// Maximum length of target string
#define child 130					// no. of children of a node in TRIE

/* constants for a random number generator, for details see numerical recipes in C */

#define IA 16807
#define IM 2147483647
#define AM (1.0/IM)
#define IQ 127773
#define IR 2836
#define MASK 123459876
/* constants for a random number generator, for details see numerical recipes in C */

using namespace std;

// seed for ran01
int seed = (int) time(NULL);

//is tabu on ? 1 : on, 0:Off
int tabu_done;

char str_folder[100];
double ran01( int *idum )
/*    
      FUNCTION:       generate a random number that is uniformly distributed in [0,1]
      INPUT:          pointer to variable with the current seed
      OUTPUT:         random number uniformly distributed in [0,1]
      (SIDE)EFFECTS:  random number seed is modified (important, this has to be done!)
      ORIGIN:         numerical recipes in C
*/
{
	  long k;
	  double ans;

	  k =(*idum)/IQ;
	  *idum = IA * (*idum - k * IQ) - IR * k;
	  if (*idum < 0 ) *idum += IM;
	  ans = AM * (*idum);
	  return ans;
}

// v is target string idx, returns pair<> to access istarget
pair<int,int> calc_target_idx(int v)
{
	return make_pair(v/30,v%30);
}

struct trie
{
//	int freq_target;		// freq. of target strings
//	int istarget[10];		// which target string contains this substring -> bitwise access
	int val;				// contains the unique idx of root to this position 
//	int freq;				// total frequency of this substring
	trie *next[child];
	trie()
	{
		int i;
		val=-1;
//		memset(istarget,0,sizeof(istarget));
		for(i=0;i<child;i++)
			next[i]=NULL;
	}
	~trie()
	{
		int i;
		for(i=0;i<child;i++)
			delete next[i];
	}
};

//if q<=q0 then in ACS the best solution is selected
const double q0 = 0.25;	
//prob of best
const double p_best = 0.09;
double t_max, t_min;					//Max, Min limit of pheromone value
//this is not used -> will not work for MMAS
const double minus_pheromone = 0.0;					//total amount of evaporation in a run
//so it is made const. zero, so don't need to change anything in select_jump
/********************************/
double alpha, beta, evaporation_rate;	
double allowed_time;						//may need to read from input
int sub_freq[Distinct_Substr];				//total freq. of substring w.r.t. it's id
int sub_freq_target[Distinct_Substr];		//freq. of target strings who contain id-th substr
int sub_is_target[Distinct_Substr][22];		//bitmap -> 1 -> which targets contain this id
pair<int,int> sub_start[Distinct_Substr];
pair<int,int> sub_end[Distinct_Substr];
int sub_tabu[Distinct_Substr];				//substring -> tabu or not
int tabu_active;							//marker of active tabu
trie *root;
int L;										//L of L-cover
int id;										//gives id to a substring
int n;										//number of target strings
int m;										//maximum length of a string
int max_len_in_all;							//maximum length of a substring which is a substring of every target string
int max_allowed_substr_length;				//in solution set
int min_allowed_substr_length;				//in solution set
char toBeCovered[T][M];						//target strings
int target_length[T];
double sqrt_m;
ofstream output,output_best;

struct node
{
//	int length;
	double cost;
	int substr_idx;
	double pheromone, eta, probability, cum_prob;
	double eta1, eta2;
	void init(int length)
	{
		pheromone = 10.0;
		//cost = 1.0;
		if(length > max_allowed_substr_length)
			cost = inf;
		//else if(length > m/4)
		//	cost = 1.2;
		else if(length < min_allowed_substr_length)
			cost = inf;

//		else if(length==2)
//			cost = 1.5;
		else
			cost = 1.0;
		eta = (0.001 * eta1 + 0.999 * eta2 * sqrt(length / sqrt_m) ) / cost; 
		//eta = (0.0995 * eta1 + 0.9 * (eta2) + 0.0005* (length)/(sqrt_m) ) / cost;
		//eta = (0.001 * eta1 + 0.999 * (eta2) ) / cost; //instances_100_a4_s20-30_l3-10_L50-100
	//	eta = sub_freq[substr_idx]/(id + 0.0);	// needs change
	}
};
		//targetidx pos	
vector<node> adj[T][M];					//vector of edges from [T][M] 
node all_node[1000005];					//just a list of all nodes according to id

struct solution
{
	double cost;						//cost or fitness of this solution
	set<int> substr_list;				//set of ids of the substrings
	vector< pair<int,int> > jumps;		//represents the jumps -> <target_string_idx, pos>
	void init()
	{
		substr_list.clear();
		jumps.clear();
	}
	void calc_cost()
	{
		int i;
		cost = 0.0;
		vector<int> now_here(substr_list.begin(),substr_list.end());
		for(i=0;i<now_here.size();i++)
			cost += all_node[now_here[i]].cost;
	//	printf("calc cost ok \n");
	}
}global_best, local_best, current;


void addtoTrie(trie *now,int i,int j,int pos)
{
//	if(pos-j+1>13)
//		return;
	if(!toBeCovered[i][pos])
		return;

	pair<int,int> access_target = calc_target_idx(i);
	int temp_idx;	
	int v = toBeCovered[i][pos];
	if(!now->next[v])
	{
		now->next[v] = new trie();
		now->next[v]->val = id++;
		
	//	node temp;
	//	temp.substr_idx = now->next[v]->val;
	//	temp.init();
	//	all_node[temp.substr_idx] = temp;

	//	now->next[v]->freq = 1;
		temp_idx = now->next[v]->val;
		sub_freq[temp_idx] = 0;
		sub_freq_target[temp_idx] = 0;
		memset(sub_is_target[temp_idx],0,sizeof(sub_is_target[temp_idx]));
	}
	
	temp_idx = now->next[v]->val;
	sub_freq[temp_idx]++;
	sub_start[temp_idx] = make_pair(i,j);
	sub_end [temp_idx]  = make_pair(i,pos);
	if( !(sub_is_target[temp_idx][access_target.first] & (1<<access_target.second)) )
		sub_is_target[temp_idx][access_target.first] |= (1<<access_target.second),
		sub_freq_target[temp_idx]++;
/*
	if( !(now->next[v]->istarget[ access_target.first ] & (1<<access_target.second)))
		now->next[v]->istarget[ access_target.first ] |= (1<<access_target.second),
		now->next[v]->freq_target++;
*/
	//sub_freq[now->next[v]->val] = now->next[v]->freq;
	
	node temp;
	temp.substr_idx = now->next[v]->val;
	adj[i][j].push_back(temp);

	addtoTrie(now->next[v],i,j,pos+1);
}

void buildGraph()
{
//	all_node.clear();
	root = new trie();
	root->val = id++;
	int i,j;
	id = 0;
	for(i=0;i<n;i++)
		for(j=0;toBeCovered[i][j];j++)
		{
			adj[i][j].clear();
			addtoTrie(root,i,j,j);
		}
//	printf("build graph ok \n");
}

void initialize_pheromone()
{
	int i,j,k;
	for(i=0;i<n;i++)
		for(j=0;toBeCovered[i][j];j++)
		{
			for(k=0;k<adj[i][j].size();k++)
			{
				adj[i][j][k].init(k+1);
				all_node[adj[i][j][k].substr_idx] = adj[i][j][k];
			}
		}
	//	printf("initialze pheromone ok \n");
}

/**********************************************/ 
// may be useful for L-cover
int mark_now;
int target_is_cover;				// idx of target string for is_cover
//	    target_idx from to
char dp_is_cover[T][M][M];			// is it possible to cover [from, to] within a finite cost?

int is_cover(int from, int to)
{
	if(to-from+1 < min_allowed_substr_length)
	{
		dp_is_cover[target_is_cover][from][to] = mark_now - 1;
		return dp_is_cover[target_is_cover][from][to];
	}
	if(to-from+1 <= max_allowed_substr_length)
	{
		dp_is_cover[target_is_cover][from][to] = mark_now;
		return dp_is_cover[target_is_cover][from][to];
	}
	if(dp_is_cover[target_is_cover][from][to] >= mark_now - 1)
		return dp_is_cover[target_is_cover][from][to];
	int i, vv;
	dp_is_cover[target_is_cover][from][to] = mark_now - 1;
	
	for(i = from + min_allowed_substr_length - 1; i < to; i++)
	{
		if( i - from + 1 > max_allowed_substr_length)
			continue;
		vv = is_cover(i+1,to);
		if( vv == mark_now)
		{
			dp_is_cover[target_is_cover][from][to] = mark_now;
			break;
		}
	}
	
	return dp_is_cover[target_is_cover][from][to];
}

void calc_is_cover(void)
{
	mark_now += 2;
	int i,j,k,ffff;
	for(i = 0; i < n; i++)
	{	
		target_is_cover = i;
		for(j = 0; toBeCovered[i][j]; j++)
			for(k = j; toBeCovered[i][k];k++)
			{
		//		dp_is_cover[i][j][k] = -1;
				ffff = is_cover(j,k);
			}
	}
}
/******************************************/

void visitTrie(trie *now,int i,int j,int pos)
{
//	if(pos-j+1>13)
//		return;
	if(!toBeCovered[i][pos])
		return;

	int v = toBeCovered[i][pos];
	adj[i][j][pos-j].eta1 = sub_freq[now->next[v]->val]/(double)(id+0.0);
	adj[i][j][pos-j].eta2 = sub_freq_target[now->next[v]->val]/(double)(n+0.0);
	
	if(sub_freq_target[now->next[v]->val] == n)
		max_len_in_all = MAX(max_len_in_all,pos-j+1);
	visitTrie(now->next[v],i,j,pos+1);
}

void calc_eta()
{
	max_len_in_all = 0;
	int i, j;
	for(i=0;i<n;i++)
		for(j=0;toBeCovered[i][j];j++)
			visitTrie(root,i,j,j);
}

int run, ant;

int select_jump(int target_idx,int pos,int flag,int interval_count)
{
//	printf("select jump enter \n");
	if(interval_count == (L-1))
		return (target_length[target_idx] - 1);
	if(target_length[target_idx] - pos <= 2*min_allowed_substr_length)
		return (target_length[target_idx] - 1);
	int i, ret_idx;
	double sum_heu = 0, max_prob = -1;
	for(i = 0; i < adj[target_idx][pos].size(); i++)
	{
		if(fabs(adj[target_idx][pos][i].cost - inf) < 1e-5)
			continue;
		if(toBeCovered[target_idx][pos+i+1] && dp_is_cover[target_idx][pos+i+1][target_length[target_idx]-1]==(mark_now - 1))
			continue;
		double now_pheromone = adj[target_idx][pos][i].pheromone - minus_pheromone;
		double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][pos][i].substr_idx ] == tabu_active);
	/*	if(flag)
		{
			now_pheromone = MAX(t_min,now_pheromone);
			now_pheromone = MIN(t_max,now_pheromone);
		} */
		sum_heu += ( pow(now_pheromone, alpha) * pow(adj[target_idx][pos][i].eta, beta) * tabu_factor);
	}
	for(i = min_allowed_substr_length - 1; i < adj[target_idx][pos].size(); i++)
	{
		if(fabs(adj[target_idx][pos][i].cost - inf) < 1e-5)
		{
			adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i-1].cum_prob;
			continue;
		}
		if(toBeCovered[target_idx][pos+i+1] && dp_is_cover[target_idx][pos+i+1][target_length[target_idx]-1]==(mark_now - 1))
		{
			adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i-1].cum_prob;
			continue;
		}
		double now_pheromone = adj[target_idx][pos][i].pheromone - minus_pheromone;
		double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][pos][i].substr_idx ] == tabu_active);
	/*	if(flag)
		{
			now_pheromone = MAX(t_min,now_pheromone);
			now_pheromone = MIN(t_max,now_pheromone);
		}*/
		double neumerator = pow(now_pheromone, alpha) * pow(adj[target_idx][pos][i].eta, beta) * tabu_factor;
		adj[target_idx][pos][i].probability =  neumerator / sum_heu;

		if(adj[target_idx][pos][i].probability > max_prob)
			max_prob = adj[target_idx][pos][i].probability,
			ret_idx = i + pos;

		if(i == min_allowed_substr_length - 1)
			adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i].probability;
		else
			adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i].probability + adj[target_idx][pos][i-1].cum_prob;
	}
	//int seed;
	//seed = (long int) time(NULL);

	if(flag%2 == 0)
	{
		double q = ran01(&seed);
		if(q < q0)
			return ret_idx;
	}

	double random_select = ran01(&seed);

	for(i=0;i<adj[target_idx][pos].size();i++)
	{
		if(fabs(adj[target_idx][pos][i].cost - inf) < 1e-5)
			continue;
		if(toBeCovered[target_idx][pos+i+1] && dp_is_cover[target_idx][pos+i+1][target_length[target_idx]-1]==(mark_now - 1))
			continue;

		if(adj[target_idx][pos][i].cum_prob >= (random_select - 1e-12) )
			return i+pos;
	}
}

int select_backjump(int target_idx,int pos,int flag,int interval_count)
{
	if(interval_count == (L-1))
		return 0;
	if(pos + 1 <= 2*min_allowed_substr_length)
		return 0;
	int i, ret_idx;
	double sum_heu = 0, max_prob = -1;
	for(i = pos; i >= 0 ; i--)
	{
		if(fabs(adj[target_idx][i][pos - i].cost - inf) < 1e-5)
			continue;
		if(i && dp_is_cover[target_idx][0][i-1]==(mark_now - 1))
			continue;
		double now_pheromone = adj[target_idx][i][pos - i].pheromone - minus_pheromone;
		double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][i][pos - i].substr_idx ] == tabu_active);
	
		sum_heu += ( pow(now_pheromone, alpha) * pow(adj[target_idx][i][pos - i].eta, beta) * tabu_factor);
	}
	for(i = pos; i >= 0 ; i--)
	{
		if(fabs(adj[target_idx][i][pos - i].cost - inf) < 1e-5)
			continue;
		if(i && dp_is_cover[target_idx][0][i-1]==(mark_now - 1))
			continue;
		double now_pheromone = adj[target_idx][i][pos - i].pheromone - minus_pheromone;
		double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][i][pos - i].substr_idx ] == tabu_active);
		double numerator = ( pow(now_pheromone, alpha) * pow(adj[target_idx][i][pos - i].eta, beta) * tabu_factor);
		adj[target_idx][i][pos - i].probability = numerator/sum_heu;

		if(adj[target_idx][i][pos - i].probability > max_prob)
		{
			max_prob = adj[target_idx][i][pos - i].probability;
			ret_idx = i;
		}

		if(pos - i + 1 == min_allowed_substr_length)
			adj[target_idx][i][pos - i].cum_prob = adj[target_idx][i][pos - i].probability;
		else
			adj[target_idx][i][pos - i].cum_prob = adj[target_idx][i+1][pos - i - 1].cum_prob + adj[target_idx][i][pos - i].probability;
	}
	
	if(flag%2 == 0)
	{
		double q = ran01(&seed);
		if(q < q0)
			return ret_idx;
	}

	double random_select = ran01(&seed);
	for(i = pos; i >= 0 ; i--)
	{
		if(fabs(adj[target_idx][i][pos - i].cost - inf) < 1e-5)
			continue;
		if(i && dp_is_cover[target_idx][0][i-1]==(mark_now - 1))
			continue;
		if(adj[target_idx][i][pos - i].cum_prob >= random_select - 1e-12)
			return i;
	}

	return ret_idx;
}

int construction_failure;			//not used

void construction(int ant, int flag)
{
//	printf("construction enter \n");
	//int seed;
	//seed = (int) time(NULL);
	int start_target = (int)(ran01(&seed)*n);
	start_target %= n;
	int i, pos;
	current.init();
	for(i = start_target;;)
	{
		if(rand()%2)
		{
			current.jumps.push_back(make_pair(i,0));
			pos = 0;
			int interval_count = 0;					//can not be greater than L for L-cover
			while(toBeCovered[i][pos])
			{
				int k = select_jump(i,pos,flag,interval_count);
		//		printf("select jump ok \n");
				
				current.substr_list.insert(adj[i][pos][k-pos].substr_idx);
				current.jumps.push_back(make_pair(i,k+1));
				pos = k+1;
				interval_count++;
			}
		}
		else
		{
			vector< pair<int,int> > tempv;
			pos = target_length[i] - 1;
			tempv.push_back(make_pair(i,pos+1));
			int interval_count = 0;					//can not be greater than L for L-cover
			while(pos>=0)
			{
				int k = select_backjump(i,pos,flag,interval_count);
				current.substr_list.insert(adj[i][k][pos-k].substr_idx);
				tempv.push_back(make_pair(i,k));
				pos = k-1;
				interval_count++;
			}

			reverse(tempv.begin(),tempv.end());
			for(int k = 0; k < tempv.size(); k++)
				current.jumps.push_back(tempv[k]);
		}
		i = (i+1)%n;
		if(i==start_target)
			break;
	}
	current.calc_cost();
//	printf("construntion ok \n");
}

void backward_construction(int ant, int flag)
{
	
}

void update_pheromone(int flag, solution got)			//need to modify according to flag
{
	//	printf("update pheromone enter\n");
	int i, j, k;
	double k1;
	//	fixing t_max and t_min for the solution we got here
	double tmax_d = evaporation_rate * got.cost;
	t_max = 1.0/tmax_d;
	k1 = m/2.0;					// max length of string/2 -> average length jump
	double p_dec = pow(p_best,(double) 1.0/(double)m);
	double tmin_d = (k1-1)*p_dec;
	t_min = t_max*(1-p_dec)/tmin_d;

	//	evaporate
	for(i=0;i<n;i++)
		for(j=0;toBeCovered[i][j];j++)
			for(k = 0;k<adj[i][j].size();k++)
			{
				adj[i][j][k].pheromone *= (1 - evaporation_rate);
				adj[i][j][k].pheromone = MAX(adj[i][j][k].pheromone, t_min);
				adj[i][j][k].pheromone = MIN(adj[i][j][k].pheromone, t_max);
			}
	
	// increase pheromone
	for(i=0;i<got.jumps.size();i++)
	{
		int uuu = got.jumps[i].first;			//target string index
		int vvv = got.jumps[i].second;			//current position
		if(!toBeCovered[ uuu ][ vvv ])			//reached end of this target string
			continue;	
		if(i+1>=got.jumps.size())
			continue;
		j = got.jumps[i+1].second - 1;
		 //jump position from current position
		//if(tabu_done)
		//{
		//	adj[ uuu ][ vvv ][ j - vvv].pheromone -= evaporation_rate * (1.0/got.cost);
		//}
		//else
			adj[ uuu ][ vvv ][ j - vvv].pheromone += evaporation_rate * (1.0/got.cost);

		adj[ uuu ][ vvv ][ j - vvv].pheromone = MIN(adj[ uuu ][ vvv ][ j - vvv].pheromone, t_max);
		adj[ uuu ][ vvv ][ j - vvv].pheromone = MAX(adj[ uuu ][ vvv ][ j - vvv].pheromone, t_min);
	}
	//	printf("update pheromone ok \n");
}

void output_strings_best(int run)
{
	output_best<<"Run "<<run<<endl;
	int i;
/*	for(i=0;i<global_best.jumps.size();i++)
	{
		int now_taget_idx = global_best.jumps[i].first;
		if(i+1>=global_best.jumps.size() || global_best.jumps[i+1].first!=now_taget_idx)
		{
			output_best<<endl;
			continue;
		}
		for(int j=global_best.jumps[i].second;j<global_best.jumps[i+1].second;j++)
			output_best<<toBeCovered[now_taget_idx][j];
		output_best<<" ";
	}*/
	output_best<<"Solution Set"<<endl;
	vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
	for(i=0;i<idx_list.size();i++)
	{
		int now_idx = idx_list[i];
		int target_now = sub_start[now_idx].first;
		for(int j = sub_start[now_idx].second; j<= sub_end[now_idx].second; j++)
			output_best<<toBeCovered[target_now][j];
		output_best<<endl;
	}
}

solution local_search(solution got)
{
	int tweak = n;
	solution best_local;
	best_local.cost = 1000000000;
	while(tweak--)
	{
		solution temp = got;
		int no_remove = 10;
		while(no_remove--)
		{
			int target = (int)(ran01(&seed)*n);
			target %= n;
			int i = 0;
			while(temp.jumps[i].first != target)
				i++;
			int no_partition = 0, j = i+1;
			while(j < temp.jumps.size() && temp.jumps[j].first==target)
				no_partition++,j++;

			int remove_idx = (int)(ran01(&seed)*no_partition);
			remove_idx %= no_partition;

			if(remove_idx == 0 || remove_idx == no_partition)
			{
				no_remove++;
				continue;
			}

			temp.jumps.erase(temp.jumps.begin()+i+remove_idx);

			temp.substr_list.clear();

			for(i=0;i<temp.jumps.size();i++)
			{
				if(i+1>=temp.jumps.size())
					continue;
				if(!toBeCovered[temp.jumps[i].first][temp.jumps[i].second])
					continue;
				j = temp.jumps[i+1].second - 1 - temp.jumps[i].second;
				temp.substr_list.insert(adj[temp.jumps[i].first][temp.jumps[i].second][j].substr_idx);
			}

			temp.calc_cost();

			if(temp.cost<best_local.cost)
				best_local = temp;
		}
	}
	return best_local;
}

/*
// for sorting strings according to size, then alphabetical order
bool comp(string founda,string foundb)
{
	if(founda.size() == foundb.size())
		return founda < foundb;
	return founda.size() < foundb.size();
}
*/

// for sorting idx_list according to eta
bool comp_substring_eta(int id1, int id2)
{
	return all_node[id1].eta < all_node[id2].eta;
}

void mark_tabu2(void)
{
	vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
	sort(idx_list.begin(), idx_list.end(), comp_substring_eta);
	int to_be_tabu = idx_list.size()/3, i;
	for(i = 0; i < to_be_tabu; i++)
		sub_tabu[ idx_list[i] ] = tabu_active;
}

bool comp_substring_pheromone(int id1, int id2)
{
	return all_node[id1].pheromone > all_node[id2].pheromone;
}

void mark_tabu3(void)
{
	vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
	sort(idx_list.begin(), idx_list.end(), comp_substring_pheromone);
	int to_be_tabu = idx_list.size(), i;
	for(i = 0; i < to_be_tabu; i++)
		sub_tabu[ idx_list[i] ] = tabu_active;
}

void mark_tabu(void)
{
	vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
	vector<string> string_list;
	int i,j;
	for(i = 0; i < idx_list.size(); i++)
	{
		int temp_idx = idx_list[i];
		int target_idx = sub_start[temp_idx].first;
		char temp_s[1000];
		for(j = sub_start[temp_idx].second; j <= sub_end[temp_idx].second; j++)
			temp_s[ j - sub_start[temp_idx].second ] = toBeCovered[target_idx][j];
		temp_s[ j - sub_start[temp_idx].second ] = 0;

		string_list.push_back(temp_s);
	}
//	sort korle accordingly idx_list o update korte hobe.	
//	sort(string_list.begin(),string_list.end(),comp());
	
	int cnt_tabu = 0;
	for(i = 0; i < string_list.size(); i++)
		for(j = 0; j < string_list.size(); j++)
		{
			if(j == i)
				continue;
			if(string_list[i].size() == 1)
				continue;
			int vvv = (int)string_list[j].find(string_list[i]);
			if(vvv != -1)												// found i in j	
			{
		//		if(rand()%2)
		//			continue;
				if(rand()%5)
					sub_tabu[ idx_list[i] ] = tabu_active;					// tabu it
				else
					sub_tabu[ idx_list[j] ] = tabu_active;
				cnt_tabu++;
			}			
		}

		if(cnt_tabu <= idx_list.size()/5)
			mark_tabu2();
}

void ACO(int flag)					// flag - 0 - ACS, 1 - MMAS, 2 - Hybrid
{
	calc_eta();
	initialize_pheromone();
	
	calc_is_cover();	
	int iter,iter_best;
	double best_time;
	
	for(run = 1; run <= MAX_RUN; run++)
	{
	/*	minus_pheromone = 0.0;	-> not used */
		tabu_done = 0;
		global_best.cost = 100000000;
		double st_time = time(NULL);
		int idx_fgb = 0;
		initialize_pheromone();
		iter = 0;
		int no_change = 0;

		int last_tabu_on = 0;
		int local_best_all = 100000000;
		while(1)
		{
			local_best.cost = 100000000;
			for(ant = 1; ant <= POPULATION_SIZE; ant++)
			{
				srand(iter*iter + rand()%100);
				construction(ant, flag);
			//	solution from_local = local_search(current);
			//	if(from_local.cost < current.cost)
			//		current = from_local;
		//		printf("%lf\n",current.cost);
				if(current.cost<local_best.cost)
					local_best = current;
		//		if(flag == 0)						// for ACS 
		//			update_pheromone(flag);
			}
			if(local_best.cost == local_best_all)
				no_change++;
			else{
				local_best_all = local_best.cost;
				no_change = 0;
			}
/*
			if(rand()%7 == 0)
			{
				solution from_local = local_search(local_best);
				if(from_local.cost < local_best.cost)
					local_best = from_local;
			}
			*/
			if(local_best.cost < global_best.cost)
			{
				//solution from_local = local_search(local_best);
				//if(from_local.cost < local_best.cost)
				//	local_best = from_local;
				global_best = local_best;
				double nd_time = time(NULL);
				double elapsed = (nd_time - st_time);
				iter_best = iter;
				best_time = elapsed;
				//no_change = 0;
			}
			//else
			//	no_change++;

			//schedule for tabu
			if(tabu_done > 0)
				tabu_done++;
			
		/*	if((no_change > NO_UPDATE/4) && (tabu_done==0) && ((iter - last_tabu_on) > NO_UPDATE/4))
			{
				printf("here tabu on iteration %d\n tabu_idx %d\n",iter,tabu_active);
				tabu_done = 1;
				
				if(rand()%2 == 0)
					mark_tabu();
				//else
				{
					if(rand()%3 == 0)
						mark_tabu2();
					//else
						mark_tabu3();
				}
			}

			if(tabu_done > NO_UPDATE/2)
			{
				printf("here tabu off %d iteration %d\n",tabu_done,iter);
				tabu_done = 0;
			
				tabu_active++;
			}
			
			if(tabu_done)
				last_tabu_on = iter;*/
			// FOR both ACS and MMAS
			// Scheduling
			int fgb[] = {7,6,5,4,3,2,1};
			int iter_fgb[] = {25,50,100,200,300,400,10000000};
			
		/*	if(iter > 120 && iter%50 == 0)
			{
				beta -= alpha;
				if(beta < alpha)
					beta = alpha + 1;
			}*/
			if(iter > iter_fgb[idx_fgb])
				idx_fgb++;

			if(iter%fgb[idx_fgb]==0 && iter>150)
				update_pheromone(flag, global_best);                         
			else
				update_pheromone(flag, local_best);
		
			iter++;
			
			printf("iteration %d global_best %lf %d local_best %lf\n",iter,global_best.cost,global_best.substr_list.size(),local_best.cost);
			if(no_change > NO_UPDATE)
			{
				// record
				break;
			}

			double nd_time = time(NULL);
			double elapsed = (nd_time - st_time);
			if(elapsed > allowed_time)
			{
				// record
				break;
			}
		}
		output<<"Run "<<run<<endl;
		output<<iter_best<<" "<<best_time<<" "<<global_best.substr_list.size()<<endl;
		output_strings_best(run);
	}
}

int readInput(int fileidx)
{
	/*if(scanf("%d",&n)!=1)						// number of target strings
		return 0;*/
	int i;
	m = 0;
	n = 10; //all set length 100
	for(i=0;i<n;i++)
	{
		scanf("%s",toBeCovered[i]);
		int v = strlen(toBeCovered[i]);
		m = MAX(v,m);
		target_length[i] = v;
	}
	sqrt_m = sqrt((double)m);
	max_allowed_substr_length = m/2;
	min_allowed_substr_length = 3;
	return 1;
}

void parameterRead(int fileidx)
{
	char str[55];
	sprintf(str,"input\\param%.2d.txt",fileidx);
	freopen(str,"r",stdin);
	scanf("%lf%lf%lf",&alpha,&beta,&evaporation_rate);
	scanf("%d",&L);
	scanf("%lf",&allowed_time);
//	fclose(fp);
}

void init_output_file(int fileidx)
{
	char str[200];
	sprintf(str,"output\\%s\\outputtest%.2d.txt",str_folder,fileidx);
	output.open(str);
	sprintf(str,"output\\%s\\outputbest%.2d.txt",str_folder,fileidx);
	output_best.open(str);
}

int main()
{
	int fileidx;
	//scanf("%d",&fileidx);
	char str_command[100];
	strcpy(str_folder,"instances_10_a50_s2-10_l3-10_L50-100");
	sprintf(str_command,"mkdir output\\%s",str_folder);
	system(str_command);
	for(fileidx = 2; fileidx <= 50; fileidx+=2)
	{
		//parameterRead(fileidx);
			
		init_output_file(fileidx);
		char str[200];
		
		sprintf(str,"instances\\%s\\instance%.2d",str_folder,fileidx);
		freopen(str,"r",stdin);
	//	while(readInput(fileidx))
		{
			readInput(fileidx);
			buildGraph();
			alpha = 5.0;
			beta = 20.0;
			evaporation_rate = 0.02;
			L = 200;
			allowed_time = 7200;

			output<<"alpha "<<alpha<<" beta "<<beta<<" evaporation_rate "<<evaporation_rate<<" with tabu"<<endl;
			output_best<<"alpha "<<alpha<<" beta "<<beta<<" evaporation_rate "<<evaporation_rate<<" with tabu"<<endl;
			tabu_active++;
			ACO(2);
	/*		beta += 0.5;
			output<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
			output_best<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
			ACO(2);
			evaporation_rate -= 0.005;
			output<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
			output_best<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
			ACO(2);*/
		}
		output.close();
		output_best.close();
	}
	return 0;
}