3106943_wa.cc

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

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

struct node
{
	char str[260];
}dic[100001];
int cnt;

int cmp(const void *a,const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;

	return strcmp(aa->str,bb->str);
}

int usable(char str[])
{
	int i;

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

void inputDic()
{
	char tmp[260];

	cnt = 0;
	while(gets(tmp)!=NULL&&strlen(tmp)!=0)
	{
		if(strlen(tmp)<256&&usable(tmp))
		{
			strcpy(dic[cnt++].str,tmp);
		}
	}
}

void change(char str[])
{
	int i;

	for(i = 0; str[i]; i++)
	{
		if(str[i]=='a')
			str[i] = 'z';
		else
			str[i]--;
	}
}

void solve()
{
	int k, i, it, j, len, now;
	int last, prev[260], out[260], tt[260];
	int best[260], min, ans, K;
	char tmp[260], str[260];

	while(gets(tmp)!=NULL&&strcmp(tmp,"0")!=0)
	{
		len = strlen(tmp);
		ans = inf;
		for(k = 0; k < 26; k++)
		{
			for(i = 0; i <= len; i++)
			{
				best[i] = inf;
			}
			best[0] = 0;
			for(i = 1; i <= len; i++)
			{
				min = inf;
				for(j = 0; j < i; j++)
				{
					strncpy(str,&tmp[j],i-j);
					str[i-j] = '\0';
					if(best[j]!=inf&&bsearch(str,dic,cnt,sizeof(dic[0]),cmp)!=NULL)
					{
						if(best[j]+1<min)
						{
							min = best[j]+1;
							last = j;
						}
					}
				}
				best[i] = min;
				prev[i] = last;
			}
			change(tmp);
			if(best[len] < ans)
			{
				last = 0;
				i = len;
				while(i!=0)
				{
					now = i - prev[i];
					if(last==1&&now==1)
					{
						break;
					}
					else
					{
						i = prev[i];
						last = now;
					}
				}
				if(i!=0||len <= 2*best[len])
					continue;
				else
				{
					ans = best[len];
					K = k;
					memcpy(out,prev,sizeof(prev));
				}
			}
		}
		if(ans==inf)
			puts("NO SOLUTIONS");
		else
		{
			printf("k=%d:",K);
			while(K--)
			{
				change(tmp);
			}
			i = len;
			tt[0] = len;
			it = 1;
			while(i!=0)
			{
				i = out[i];
				tt[it++] = i;
			}
			for(i = it-1; i > 0; i--)
			{
				putchar(' ');
				for(j = tt[i]; j < tt[i-1]; j++)
				{
					putchar(tmp[j]);
				}
			}
			putchar('\n');
		}
	}
}

int main()
{
	inputDic();
	qsort(dic,cnt,sizeof(dic[0]),cmp);
	solve();
	return 0;
}