#include <iostream>
using namespace std;
char p[25005][30];
int path[25005];
int aim;
struct node
{
	int count;//字符串长度
	int index;
	node *ptr[26];
	node()
	{
		index=-1;
		count=0;
		for(int i=0;i<26;i++)
			ptr[i]=NULL;
	};
}root;
void insert(char *s)
{
	int i, len=strlen(s);
	node* p=&root;
	for(i=0;i<len;i++)
	{
		if(p->ptr[s[i]-'a']==NULL)
		{
			p->ptr[s[i]-'a']=new node();
		}
		p=p->ptr[s[i]-'a'];	
	}
	p->count=len;
	p->index=aim;
}
int find(char *s)
{
	int i,len=strlen(s);
	node *p=&root;
	for(i=0;i<len;i++)
	{
		if(p->ptr[s[i]-'a']==NULL)
		{
			return -1;
		}
		p=p->ptr[s[i]-'a'];
	}
	if(p->count==len)
	return p->index;
	else return -1;
}
void change(int x)
{
	int len=strlen(p[x]);
	int i,j;
	char z;
	int vv;
	char temp[30];
	for(j=0;j<len;j++)
	{
		temp[j]=p[x][j];
	}
	temp[len]='\0';
	for(i=0;i<len;i++)
	{
		for(z='a';z<='z';z++)
		{	
			if(z==p[x][i])
			{
				continue;
			}
			temp[i]=z;	
		if(strcmp(p[x],temp)>0)
		{
			continue;
		}
		vv=find(temp);
		if(vv>=0)
		{
		if(path[vv]<path[x]+1)
		{
			path[vv]=path[x]+1;
		}
		}
		}
		temp[i]=p[x][i];
	}
}
void deletes(int x)
{
	int vv;
	char temp[30];
	int i,j,k;
	int len=strlen(p[x]);
	if(len==1)
	{
		return;
	}
	for(i=0;i<len;i++)
	{
		k=0;
		for(j=0;j<len;j++)
		{
			if(j==i)
			{
				continue;
			}
			temp[k++]=p[x][j];
		}
		temp[k]='\0';
		if(strcmp(p[x],temp)>0)
		{
			continue;
		}
		vv=find(temp);
		if(vv>=0)
		{
		if(path[vv]<path[x]+1)
		{
			path[vv]=path[x]+1;
		}
		}
	}
}
void add(int x)
{
	int vv;
	int len=strlen(p[x]);
	int i;
	char z;
	char temp[30];
	int k;
	for(i=0;i<=len;i++)
	{
		for(z='a';z<='z';z++)
		{
			for(k=0;k<i;k++)
			{
				temp[k]=p[x][k];
			}
			temp[i]=z;
			for(k=i+1;k<=len;k++)
			{
				temp[k]=p[x][k-1];
			}
			temp[len+1]='\0';
			if(strcmp(p[x],temp)>0)
			{
				continue;
			}
			vv=find(temp);
			if(vv>=0)
			{
				if(path[vv]<path[x]+1)
				{
					path[vv]=path[x]+1;
				}
			}
		}
	}
}
int main()
{

	int i,sum;
	i=0;
	aim=0;
	while(scanf("%s",p[i])!=NULL&&p[i][0]!='.')
	{
		insert(p[i]);
		aim++;
		i++;
	}
	sum=i;
	for(i=0;i<sum;i++)
	{
		path[i]=1;
	}
	for(i=0;i<sum;i++)
	{
		add(i);
		deletes(i);
		change(i);
	}
	int maxs=0;
	for(i=0;i<sum;i++)
	{
		if(path[i]>maxs)
		{
			maxs=path[i];
		}
	}
	printf("%d\n",maxs);
	return 0;
}

• 输入写错了 贡献了N个RE。。。 (2854) ACM_henry 2008-11-01 21:00:06