3104846_ac_1093ms_10260k.c

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

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

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

void setNull(trie *t)
{
	int i;

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

int best[25001];
int ans, cnt;

void addWord(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]=='{')
		{
			t->id = cnt;
			return ;
		}
		else
			addWord(t->next[str[0]-'a'],&str[1]);
	}
	else
	{
		if(str[0]=='{')
		{
			t->id = cnt;
			return ;
		}
		else
			addWord(t->next[str[0]-'a'],&str[1]);
	}

}

int findWord(trie *t,char str[])
{
	if(str[0]=='{')
	{
		if(t->next['{'-'a']==NULL)
			return -1;
		else
			return t->id;
	}
	else
	{
		if(t->next[str[0]-'a']==NULL)
			return -1;
		else
			return findWord(t->next[str[0]-'a'],&str[1]);
	}
}

int main()
{
	int i, id, max;
	char ch, tt, tmp[20], bak[20];
	trie *t;

	ans = 0;
	cnt = 0;
	t = INIT;
	setNull(t);
	while(scanf("%s",tmp)==1)
	{
		strcat(tmp,"{");
		if(cnt==0)
		{
			addWord(t,tmp);
			max = 1;
		}
		else
		{
			max = 1;
			for(ch = 'a'; ch <= 'z'; ch++)
			{
				for(i = 0; tmp[i]!='{'; i++)
				{
					tt = tmp[i];
					tmp[i] = ch;
					id = findWord(t,tmp);
					tmp[i] = tt;
					if(id!=-1&&best[id]+1>max)
					{
						max = best[id]+1;
					}
					strcpy(bak,tmp);
					strcpy(&bak[i],&bak[i+1]);
					id = findWord(t,bak);
					if(id!=-1&&best[id]+1>max)
					{
						max =  best[id]+1;
					}
				}
				strcpy(&bak[1],tmp);
				bak[0] = ch;
				for(i = 1; bak[i]!='{'; i++)
				{
					id = findWord(t,bak);
					if(id!=-1&&best[id]+1>max)
					{
						max = best[id]+1;
					}
					bak[i-1] = bak[i];
					bak[i] = ch;
				}
				id = findWord(t,bak);
				if(id!=-1&&best[id]+1>max)
				{
					max = best[id]+1;
				}
			}
			addWord(t,tmp);
		}
		best[cnt] = max;
		if(max > ans)
		{
			ans = max;
		}
		cnt++;
	}
	printf("%d\n",ans);
	return 0;
}