3103825_wa.c

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INIT (trie *)malloc(sizeof(trie))
#define inf 2100000000

typedef struct node
{
	struct node *next[27];
}trie;

void setNull(trie *t)
{
	int i;

	for (i = 0; i < 27; i++)
		t->next[i] = NULL;
}

void addWords(trie *t,char str[])
{
	trie *p;

	if (t->next[str[0]-'a']==NULL)
	{
		p = INIT;
		setNull(p);
		t->next[str[0]-'a'] = p;
		if (str[0]=='{')
		{
			return ;
		}
		else
			addWords(t->next[str[0]-'a'],&str[1]);
	}
	else
	{
		if(str[0]=='{')
			return ;
		else
			addWords(t->next[str[0]-'a'],&str[1]);
	}
}

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

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

void getDic(trie *t)
{
	// '{' means the end of a word;
	char tmp[10000];
	
	while(gets(tmp)!=NULL&&strlen(tmp)!=0)
	{
		if(strlen(tmp)<256&&usable(tmp))
		{
			strcat(tmp,"{");
			addWords(t,tmp);
		}
	}
}

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

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

int findWords(trie *t,char mes[],int len)
{
	if(len==0)
	{
		return t->next['{'-'a']!=NULL;
	}
	else
	{
		if(t->next[mes[0]-'a']==NULL)
			return 0;
		else
			return findWords(t->next[mes[0]-'a'],&mes[1],len-1);
	}
}

void solve(char mes[],trie *t)
{
	int i, j, k, K;
	int len, min, now, last;
	int best[260], prev[260], ans[260];
	int out[260], it;

	len = strlen(mes);
	min = inf;
	for(k = 0; k < 26; k++)
	{
		memset(best,-1,sizeof(best));
		best[0] = 0;
		for(i = 1; i <= len; i++)
		{
			for(j = 0; j < i; j++)
			{
				if(best[j]!=-1&&findWords(t,&mes[j],i-j))
				{
					if(best[i]==-1||best[i]>best[j]+1)
					{
						best[i] = best[j]+1;
						prev[i] = j;
					}
				}
			}
		}
		change(mes);
		if(best[len]!=-1&&best[len] < min)
		{
			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
			{
				min = best[len];
				K = k;
				memcpy(ans,prev,sizeof(ans));
			}
		}
	}
	if(min==inf)
		puts("NO SOLUTIONS");
	else
	{
		printf("k=%d: ",K);
		while(K--)
		{
			change(mes);
		}
		i = len;
		out[0] = len;
		it = 1;
		while(i!=0)
		{
			i = ans[i];
			out[it++] = i;
		}
		for(i = it-1; i > 0; i--)
		{
			for(j = out[i]; j < out[i-1]; j++)
			{
				putchar(mes[j]);
			}
			if(i==1)
				putchar('\n');
			else
				putchar(' ');
		}
	}
}

int main()
{
	int i, w;
	trie *t;
	char mes[256];
	
	t = INIT;
	setNull(t);
	getDic(t);
	while(gets(mes)!=NULL&&strcmp(mes,"0")!=0)
	{
		w = 0;
		for(i = 0; mes[i]; i++)
		{
			if(mes[i]<'a'||mes[i]>'z')
			{
				w = 1;
				break;
			}
		}
		if(w==0)
		{
			solve(mes,t);
		}
		else
		{
            while(1)
            puts("NO SOLUTIONS");
		}
	}
	return 0;
}