POJ 1318 水题累积

POJ 1318 水题积累

【题意简述】：输入一个字典，之后再输入若干单词。每输入一个单词，你都需要在字典中找出所有可以用这个单词重新排列后得到的单词，并且按照字典序从小到达进行排序输出。若不存在就输出“NOT A VALID WORD”。

注：字典中的单词并不一定按照字典序排序！

这种字符串的排序问题，不错的水题，多积累！

【思路】：1、首先我们可以将字典中的每一个单词都进行排序，这样可以直接和后来输入的单词进行比较！

  2、然后我们把所有单词按照字典序进行排序，并存入另一个数组，这就解决了输出时按字典序排序的问题

  3、最后我们只需要匹配，然后输出！

// 192K 16Ms
#include<iostream>
using namespace std;

int n;
char word[100][10],sorted[200][10];
//给每个“字符”建立比较函数 
int cmp_char(const void* _a,const void* _b)
{
	char* a = (char*)_a;
	char* b = (char*) _b;
	return *a - *b;
}
// 给 字典中的 所有的字符串建立比较函数 
int cmp_string(const void* _a,const void* _b)
{
	char* b = (char*)_b;
	char* a = (char*)_a;
	return strcmp(a,b);
}

int main()
{
	n = 0;
	for(;;)
	{
		cin>>word[n];
		if(word[n][0] == 'X') break;
		n++;
	}
	qsort(word,n,sizeof(word[0]),cmp_string);  //给字典中的字符串排序
	//给每个字符进行排序！！ 
	for(int i = 0;i<n;i++)
	{
		strcpy(sorted[i],word[i]);
		qsort(sorted[i],strlen(sorted[i]),sizeof(char),cmp_char);
	}
	
	char s[10];
	while(cin>>s)
	{
		if(strcmp(s,"XXXXXX") == 0) break;
		qsort(s,strlen(s),sizeof(char),cmp_char);//为输入的单个字符进行排序！ 
		int found = 0;
		for(int i = 0;i<n;i++)
			if(strcmp(sorted[i],s) == 0)
			{
				found = 1;
				cout<<word[i]<<endl;
			}
		if(!found) cout<<"NOT A VALID WORD"<<endl;
		cout<<"******"<<endl;
	}
	return 0;
}