2574049_ac_45ms_220k.cpp

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

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n;
struct node
{
	int len;
	char str[81];
}word[1001];

vector <int> tree[1001];
int visited[1001], max;
char ans[81];

bool cmp(struct node a,struct node b)
{
	return a.len<b.len;
}

int check(int i,int j)
{
	int k;

	for(k = 0; k < word[j].len; k++)
		if(word[j].str[k]!=word[i].str[k])
			return strcmp(&word[i].str[k],&word[j].str[k+1])==0;
	return 1;
}

void dfs(int v,int n)
{
	int i;
	int mark;

	mark = 1;
	visited[v] = 1;
	for(i = 0; i < tree[v].size(); i++)
	{
		if(!visited[tree[v][i]])
		{
			mark = 0;
			dfs(tree[v][i],n+1);
		}
	}
	if(mark&&n>max)
	{
		max = n;
		strcpy(ans,word[v].str);
	}
}

int main()
{
	int i, j;

	scanf("%d%s",&n,word[0].str);
	word[0].len = strlen(word[0].str);
	for(i = 1; i <= n; i++)
	{
		scanf("%s",word[i].str);
		word[i].len = strlen(word[i].str);
	}
	sort(&word[1],&word[1]+n,cmp);
	memset(visited,0,sizeof(visited));
	for(i = 0; i <= n; i++)
		for(j = i+1; j <= n; j++)
		{
			if(word[j].len==word[i].len+1&&check(i,j))
				tree[i].push_back(j);
		}
	max = -1;
	dfs(0,0);
	puts(ans);
	return 0;
}