2138.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
//#include<iostream>
//#include<tchar>
//#include "stdafx.h"

#define NMAX 1003

#define LEN 10

//using namespace std;

//string k;
char basestr[90];
int n;
typedef struct
{
	char str[90];
	int len;
}data;
data p[NMAX];
int m[NMAX]={0};
int baseno;
bool f[NMAX];
int cmp(const void *a,const void *b)
{
	return ((data*)a)->len-((data*)b)->len;
}
bool scmp(data a,data b)
{
	int i;
	bool flag=0;
	for(i=0;i<a.len;i++)
	{
		if(flag==0)
		{
			if(a.str[i]!=b.str[i])
				flag=1;
		}
		if(flag==1)
		{
			if(b.str[i]!=a.str[i+1])
				return 0;
		}
	}
	return 1;
}
void solve()
{
	qsort(p,n,sizeof(data),cmp);
	int i,j;
	for(i=0;i<n;i++)
	{
		if(!strcmp(basestr,p[i].str))
			baseno=i;
	}
	m[baseno]=1;
	f[baseno]=1;
	for(i=baseno+1;i<n;i++)
	{
		for(j=i-1;p[i].len-p[j].len<=1;j--)
		{
			if(j<baseno)
				break;
			if(p[i].len==p[j].len)
				continue;
			if(!scmp(p[i],p[j]))
				continue;
			if(m[i]<m[j]+1&&f[j])
			{
				m[i]=m[j]+1;
				f[i]=1;
			}

		}
	}
	int max=-1;
	int index=-1;
	for(i=baseno;i<n;i++)
	{
		if(max<m[i])
		{
			max=m[i];
			index=i;
		}
	}
	printf("%s",p[index].str);


}

main()
{
#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i;
	
	scanf("%d ",&n);
	gets(basestr);
	for(i=0;i<n;i++)
	{
		gets(p[i].str);
		p[i].len=strlen(p[i].str);
		
	}
	solve();
	
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}