4128501_ac_547ms_6840k.cpp

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

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

using namespace std;
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[10001], prev[10001];
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]);
	}
}

struct Node
{
	char words[21];
	char tmp[21];
	bool operator < (const Node &t)	const
	{
		return strlen(tmp) < strlen(t.tmp);
	}
}nn[10001];

int main()
{
	int i, id, max;
	char bak[21];
	trie *t;
	int last, st;

	ans = 0;
	cnt = 0;
	t = INIT;
	setNull(t);
	while(scanf("%s",nn[cnt].tmp)==1)
	{
		strcpy(nn[cnt].words, nn[cnt].tmp);
		sort(nn[cnt].tmp, nn[cnt].tmp + strlen(nn[cnt].tmp));
		strcat(nn[cnt].tmp, "{");
		cnt++;
	}
	int tt = cnt;
	sort(nn, nn + cnt);
	for (cnt = 0; cnt < tt; cnt++)
	{
		max = 1;
		last = -1;
		if(cnt == 0)
		{
			addWord(t,nn[cnt].tmp);
		}
		else
		{
			for (i = 0; nn[cnt].tmp[i] != '{'; i++)
			{
				strcpy(bak, nn[cnt].tmp);
				strcpy(&bak[i], &bak[i + 1]);
				id = findWord(t, bak);
				if (id != -1 && best[id] + 1 > max)
				{
					max = best[id] + 1;
					last = id;
				}
			}
			addWord(t, nn[cnt].tmp);
		}
		best[cnt] = max;
		prev[cnt] = last;
		if(max > ans)
		{
			ans = max;
			st = cnt;
		}
	}
	vector <int> res;
	while (st != -1)
	{
		res.push_back(st);
		st = prev[st];
	}
	for (i = res.size() - 1; i >= 0; i--)
	{
		puts(nn[res[i]].words);
	}
	return 0;
}