1277 全文检索.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//VC++
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

char text[60010];
char key[10010][71];
char buffer[10010];
vector< vector<int> > hash;
struct rank
{
	int num,pos;
	bool operator < (const rank & temp) const
	{
		return pos<temp.pos;
	}
}findpos[10010];
int n,m;

int main()
{
	int i,j,t,len,pos,keylen,numkey,all;
	bool flag;
	
	hash.resize(10010);
	while(scanf("%d %d", &n, &m) == 2)
	{
		for(i=0;i<10010;i++)
			hash.clear();
		text[0]=0;
		getchar();
		for(i=0;i<n;i++)
		{
			gets(buffer);
			strcat(text,buffer);
		}
		len=strlen(text);
		t=(text[0]-'0')*1000+(text[1]-'0')*100+(text[2]-'0')*10+(text[3]-'0');
		hash[t].push_back(i);
		for(i=1;i<len;i++)
		{
			t-=(text[i-1]-'0')*1000;
			t*=10;t+=(text[i+3]-'0');
			hash[t].push_back(i);
		}
		getchar();
		for(i=1;i<=m;i++)
		{
			scanf("[Key No. %d] ",&t);
			gets(key[i]);
		}
		all=0;
		for(i=1;i<=m;i++)
		{
			numkey=(key[i][0]-'0')*1000+(key[i][1]-'0')*100+(key[i][2]-'0')*10+(key[i][3]-'0');
			flag=false;
			while( !hash[numkey].empty() )
			{
				keylen=strlen(key[i]);
				pos=hash[numkey].back();
				hash[numkey].pop_back();
				for(j=0;j<keylen;j++,pos++)
				{
					if(key[i][j]!=text[pos])
						break;
				}
				if(j==keylen)
				{	pos-=keylen;flag=true;break;}
			}
			if(flag)
			{	findpos[all].num=i;findpos[all].pos=pos;all++;}
		}//for
		sort(findpos,findpos+all);
		if(all!=0)
		{
			printf("Found key:");
			for(i=0;i<all;i++)
				printf(" [Key No. %d]",findpos[i].num);
			printf("\n");
		}
		else
			printf("No key can be found !\n");
	}
	return 0;
}