2206376_ac_574ms_288k.cc

北大大牛代码 1240道题的原代码 超级权威

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

using namespace std;

int lenth[17][2];
struct node
{
	int id;
	int len;
	char word[16];
}dic[10001], output[10001];

bool cmp(struct node a,struct node b)
{
	return a.len<b.len;
}

bool CMP(struct node a,struct node b)
{
	return a.id<b.id;
}

int check1(char a[],char b[])
{
	int i;
	char tmp[16];

	strcpy(tmp,b);
	for(i = 0; tmp[i]!='\0'; i++)
	{
		strcpy(&tmp[i],&tmp[i+1]);
		if(strcmp(tmp,a)==0)
			return 1;
		strcpy(tmp,b);
	}
	return 0;
}

int check2(char a[],char b[])
{
	int i;

	for(i = 0; b[i]!='\0'; i++)
	{
		if(a[i]==b[i])
			continue;
		else
			if(strcmp(&a[i+1],&b[i+1])==0)
				return 1;
			else
				return 0;
	}
	return 0;
}

void input()
{
	int i = 0, l, L, no, n, mark;
	char tmp[16];

	while(scanf("%s",tmp)==1&&strcmp(tmp,"#")!=0)
	{
		strcpy(dic[i].word,tmp);
		dic[i].id = i;
		dic[i++].len = strlen(tmp);
	}
	n = i;
	sort(dic,dic+n,cmp);
	for(i = 0; i < 17; i++)
		lenth[i][0] = lenth[i][1] = -1;
	l = dic[0].len;i = 0;L = dic[n-1].len;
	while(l<=L)
	{
		lenth[l][0] = i;
		while(++i<n&&dic[i].len==l);
		if(i==n)
		{
			lenth[L][1] = n-1;
			break;
		}
		else
		{
			lenth[l][1] = i-1;
			l = dic[i].len;
		}
	}
	while(scanf("%s",tmp)==1&&strcmp(tmp,"#")!=0)
	{
		mark = no = 0;
		printf("%s",tmp);
		l = strlen(tmp);
		if(lenth[l-1][0]>=0)
		{
			for(i = lenth[l-1][0]; i <= lenth[l-1][1]; i++)
				if(check1(dic[i].word,tmp))
				{
					mark = 1;
					output[no].id = dic[i].id;
					strcpy(output[no++].word,dic[i].word);
				}
		}
		if(lenth[l][0]>=0)
		{
			for(i = lenth[l][0]; i <= lenth[l][1]; i++)
			{
				if(strcmp(dic[i].word,tmp)==0)
				{
					printf(" is correct\n");
					goto con;
				}
				if(check2(dic[i].word,tmp))
				{
					mark = 1;
					output[no].id = dic[i].id;
					strcpy(output[no++].word,dic[i].word);
				}
			}
		}
		if(lenth[l+1][0]>=0)
		{
			for(i = lenth[l+1][0]; i <= lenth[l+1][1]; i++)
				if(check1(tmp,dic[i].word))
				{
					mark = 1;
					output[no].id = dic[i].id;
					strcpy(output[no++].word,dic[i].word);
				}
		}
		printf(":");
		if(mark)
		{
			sort(output,output+no,CMP);
			for(i = 0; i < no; i++)
				printf(" %s",output[i].word);
		}
		printf("\n");
con: ;
	}
}

int main()
{
	input();
	return 1;
}