#include <stdio.h>
#include <string.h>

void merge();
int isSortedSet(char *set);
int isCorrectSet(char *set);
char * get(int n, char *str);
void mergeSets(char *set1, char *set2, char *result);
void myMergeSets(char * set1, char * set2, char * word1, char * word2, char * result, char * last, int flag1, int flag2);

void main () {
	merge();
}

void merge ()
{
	char str1[257], str2[257], str[257], res[514];
	strcpy(str1,get(1,str));          // get string with get function
	strcpy(str2,get(2,str));
	mergeSets(str1, str2, res);
}

char * get(int n, char * str) {        // get and check the strings
	if (n == 1)
		printf("Enter first set of names:\n");
	if (n == 2)
		printf("Enter second set of names:\n");
	gets(str);
	if (!isCorrectSet(str) || !isSortedSet(str))
	{
		printf("Input Incorrect! Please try again.\n");
		return get(n,str);
	}
	return str;
}

int isCorrectSet(char *set) {       //check if the string is legal
	if (*set=='\0')
		return 1;
	if (((*set<'a') || (*set>'z')) && (*set != ' '))
		return 0;
	return isCorrectSet(set+1);
}

int isSortedSet(char *set)               //check if the srting is sorted by using counter
{
	char name1[257], name2[257], temp[257];
	int count1, count2;
	strcpy(temp, set);
		count1 = sscanf(temp, "%s %[^s]", name1, temp);
		count2 = sscanf(temp, "%s", name2);
		if ((count1 == 2) && count2)
		{
			if ((strcmp(name1, name2) > 0))
				return 0;
			return isSortedSet(temp);
		}
		else
			return 1;
}

void mergeSets(char *set1, char *set2, char *result) {
	char last[257], word1[257], word2[257];
	result[0] = '\0';                         // initialization the result string
	last[0] = 'A';
	sscanf(set1, "%s %[^$]", word1, set1);     // read the first word
	sscanf(set2, "%s %[^$]", word2, set2);//
	myMergeSets(set1,set2,word1,word2,result,last,0,0);      //Auxiliary function
	result[(strlen(result)-1)] = '\0';
	printf("Result:\n");
	puts(result);
}

void myMergeSets(char * set1, char * set2, char * word1, char * word2, char * result, char * last, int flag1, int flag2)
{
	if (!set1[0])               // check if set1 is empty
		flag1 = 1;
	if (!set2[0])               // check if set2 is empty
		flag2 = 1;
	if (flag1 && flag2)
		return;
	if (flag2 || (!flag1 && (strcmp(word1,word2) < 0)))    // all cases to write word1 first
	{
		if (strcmp(last,word1) != 0)
		{
			strcat(result,word1);
			strcat(result," ");
			strcpy(last,word1);
		}
		if (strcmp(word1,set1) != 0)
			sscanf(set1, "%s %[^$]", word1, set1);
		else
			flag1 = 1;
	}
	else if (flag1 || (!flag2 && (strcmp(word1,word2) > 0)))     // all cases to write word2 first
	{
		if (strcmp(last,word2) != 0)
		{
			strcat(result,word2);
			strcat(result," ");
			strcpy(last,word2);
		}
		if (strcmp(word2,set2) != 0)
			sscanf(set2, "%s %[^$]", word2, set2);
		else
			flag2 = 1;
	}
	else if (!flag1 && !flag2 && !strcmp(word1,word2))     //if word1 and word2 are same
	{
		if (strcmp(last,word2) != 0)       // confirm that the words are not the last word  that be write
		{
			strcat(result,word2);
			strcat(result," ");
			strcpy(last,word2);
		}
		if (strcmp(word2,set2) != 0)
			sscanf(set2, "%s %[^$]", word2, set2);
		else
			flag2 = 1;
		if (strcmp(word1,set1) !=0)
			sscanf(set1, "%s %[^$]", word1, set1);
		else
			flag1 = 1;
	}
	myMergeSets(set1,set2,word1,word2,result,last,flag1,flag2);
}