꿈을 꾸다...

/* 

Subject: #123 Searching Quickly

e-mail: morcavon@gmail.com

Homepage: http://www.morcavon.com

Building: 17/02/2005 ~ 18/02/2005

Last Update: 18/02/2005

*/



/*

<INPUT>

list of words to ignore

::

list of titles

-

<OUTPUT>

KWIC-index of the titles (alphabetized)

-

<CONDITION>

1 <= length of words to ignore <= 10

1 <= # of words title contains <= 15

0 <= # of words to ignore <= 50

0 <= # of titles <= 200

0 <= total length of title <= 10000

*/



#include <iostream>

#include <stdlib.h> // qsort()

#include <cstring>

#include <ctype.h>



using namespace std;





//#define ONLINE_JUDGE



struct Word

{

	char *word;

	Word *link;

	char flag : 1; // 중복된 키워드일때 이미 처리가 됐으면 1 아니면 0

};



struct KWIC

{

	char *word; // point keyword

	unsigned char idx; // index for title[]

};



int strcmpi(const char *s1, const char *s2);

int cmp(const void *s1, const void *s2);

int cmp1(const void *s1, const void *s2);

int cmp2(const void **s1, const void **s2);



int main()

{

	char w2i[50][11]; // words to ignore

	char nW2i = 0; // # of words to ignore





	//////////////////////////////////////////////////////////////////////////

	/////////////////////// Processing Words to ignore ////////////////////

	//////////////////////////////////////////////////////////////////////////

	while (cin >> w2i[nW2i]) {

		if (bsearch(w2i[nW2i], w2i, nW2i, sizeof(w2i[0]), cmp1) == NULL) {

			if (w2i[nW2i][0] == ':')

				break;

			else

				nW2i++;

		}

	}



	// 나중에 이진탐색을 하기 위해 미리 정렬해 놓자~

	qsort(w2i, nW2i, sizeof(w2i[0]), cmp);









	//////////////////////////////////////////////////////////////////////////

	/////////////////////// Processing Titles /////////////////////////////

	//////////////////////////////////////////////////////////////////////////

	/*

	title을 문자열 하나에 저장하지 않고 각 단어를 나눠서 리스트로 연결=_=

	그래야 나중에 키워드만 뽑아내기가 수월할듯...흠..

	*/

	KWIC *kwic[15 * 200];

	Word *title[200] = {0};

	char buf[256];

	unsigned char nTitle = 0; // # of titles

	int nKwic = 0; // # of KWIC-index



	while (cin.eof() == false) {



		// create head node

		title[nTitle] = new Word;

		title[nTitle]->link = NULL;



		for (Word *w_ptr = title[nTitle]; cin >> buf; w_ptr = w_ptr->link) {

			char len = strlen(buf);



			Word *new_word = new Word;

			new_word->word = new char [len + 1];

			strcpy(new_word->word, buf);

			new_word->word[len] = '\0';

			new_word->flag = 0;



			new_word->link = NULL;

			w_ptr->link = new_word;





			// keyword 유무를 체크해서 키워드 리스트를 만든당...

			if (bsearch(new_word->word, w2i, nW2i, sizeof(w2i[0]), cmp1) == NULL) {

				KWIC *new_kwic = new KWIC;



				new_kwic->idx = nTitle;

				new_kwic->word = new_word->word;



				kwic[nKwic++] = new_kwic;

			}



			if (cin.get() == '\n')

				break;

		} // end of one word



		nTitle++;



	} // end of one title (while())







	//////////////////////////////////////////////////////////////////////////

	///////////////////////////////// OUPUT ///////////////////////////////

	//////////////////////////////////////////////////////////////////////////

	qsort(kwic, nKwic, sizeof(kwic[0]), (int(*)(const void*, const void*))cmp2);



	Word *w_ptr;

	char x, flag;



	// keyword는 대문자로, keyword가 아닌 단어들은 모두 소문자로 출력

	for (int i = 0; i < nKwic; i++) {



		/* 

		flag: 현재 타이틀에서 키워드가 이미 출력됐는지 여부

		w_ptr->flag: 중복된 키워드가 있을 때 하나의 키워드만 출력하기 위한 플래그

		*/

		w_ptr = title[kwic[i]->idx]->link;

		for (flag = 0; w_ptr != NULL; w_ptr = w_ptr->link) {



			if (!strcmp(w_ptr->word, kwic[i]->word) && flag == 0 && w_ptr->flag == 0) {

				for (x = 0; w_ptr->word[x] != '\0'; x++)

					cout << (char)toupper(w_ptr->word[x]); // 대문자로 변환



				w_ptr->flag = flag = 1;

			}

			else {

				for (x = 0; w_ptr->word[x] != '\0'; x++)

					cout << (char)tolower(w_ptr->word[x]);

			}



			if (w_ptr->link != NULL)

				cout << " ";

		} // end of one word



		cout << "\n";



	} // end of one title





	return 0;

}









int cmp(const void *s1, const void *s2)

{

	// qsort에 쓸 비교함수수수수=_=

	return strcmp((const char*)s1, (const char*)s2);

}





int cmp1(const void *s1, const void *s2)

{

	// case is irrelevant if a word is to be ignored.

	return strcmpi((const char*)s1, (const char*)s2);

}





int cmp2(const void **s1, const void **s2)

{

	char x = strcmpi(((KWIC*)*s1)->word, (((KWIC*)*s2)->word));

	if (x < 0)

		return -1;

	else 

		if (x == 0) // 먼저 입력된 타이틀이 앞으로 오도록...

			return ((KWIC*)*s1)->idx - ((KWIC*)*s2)->idx;

		else

			return 1;

}





int strcmpi(const char *s1, const char *s2)

{

	// 아....이런..유닉스컴파일러라 지원을 안한다=_=;;;만들어야 한단 말인가...으

	while (*s1 != '\0' && *s2 != '\0') {

		if (tolower(*s1) != tolower(*s2))

			break;

		s1++, s2++;

	}



	return tolower(*s1) - tolower(*s2);

}