3097396_tle.c

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

#include <stdio.h>
#include <string.h>
#define inf 2100000000

char dic[100001][500];
int num, length[100001];

int check(char str[])
{
	int j;

	for(j = 0; str[j]; j++)
	{
		if(str[j] < 'a' || str[j] > 'z')
		{
			return 0;
		}
	}
	return 1;
}

int main()
{
	int suc, min, tot, flag;
	int i, j, k, K, t, len, best[259], use[259];
	char mes[259], tmp[259];
	int tans[259], cc;
	int ans[259], cnt;
	
	num = 0;
	suc = 0;
	gets(dic[0]);
	if(strlen(dic[0])==0)
	{
		while(1)
		{
			puts("wait for u");
		}
	}
	num += check(dic[0]);
	while(gets(dic[num])!=NULL)
	{
		if(strlen(dic[num])==0)
			break;
		else
			num += check(dic[num]);
	}
	for(i = 0; i < num; i++)
	{
		length[i] = strlen(dic[i]);
	}
	while(gets(mes)!=NULL)
	{
		if(mes[0]=='0')
		{
			break;
		}
		min = inf;
		for(k = 0; k < 26; k++)
		{
			for(j = 0; mes[j]; j++)
			{
				tmp[j] = mes[j] - k;
				if(tmp[j] < 'a')
				{
					tmp[j] += 26;
				}
			}
			tmp[j] = '\0';
			len = strlen(tmp);
			memset(best,-1,sizeof(best));
			best[0] = 0;
			use[0] = -1;
			for(j = 1; j <= len; j++)
			{
				if(best[j-1]==-1)
					continue;
				for(i = 0; i < num; i++)
				{
					t = j -1 + length[i];
					if(t > len)
						continue;
					if(strncmp(dic[i],&tmp[j-1],length[i])==0)
					{
						if(best[t]==-1)
						{
							use[t] = i;
							best[t] = best[j-1]+1;
						}
						else
						{
							if(best[t] > best[j-1]+1)
							{
								best[t] = best[j-1]+1;
								use[t] = i;
							}
						}
					}
				}
			}
			if(best[len]!=-1)
			{
				j = len;
				cc = 0;
				while(j!=0)
				{
					tans[cc++] = use[j];
					j -= length[use[j]];
				}
				flag = 0;
				tot = length[tans[0]];
				for(j = 1; j < cc; j++)
				{
					tot += length[tans[j]];
					if(length[tans[j]]==1&&length[tans[j-1]]==1)
					{
						flag = 1;
						break;
					}
				}
				if(flag == 1 || tot <= 2 * best[len])
					continue;
				if(best[len] < min)
				{
					K = k;
					min = best[len];
					cnt = cc;
					for(i = 0; i < cc; i++)
					{
						ans[i] = tans[i];
					}
				}
			}
		}
		if(min==inf)
			puts("NO SOLUTIONS");
		else
		{
			printf("k=%d:",K);
			for(i = cnt-1; i >= 0; i--)
			{
				printf(" %s",dic[ans[i]]);
			}
			puts("");
		}
	}
	return 0;
}