#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define size 100

int len1,len2;
char str1[size];
char str2[size];
int len[size][size];
char cur[size+size];
char ans[10000][size+size];
int top,maxlen,tops;
struct node{
	int i,j;
	int len;
};
node s[size*size];
node path[size+size];

int start[size+size];

int print()
{
	int i,j;
	for(i=0;i<=len2;i++)
	{
		for(j=0;j<=len1;j++) printf("%3d",len[i][j]);
		printf("\n");
	}
	return 12;
}

void add(int l)
{
	int i;
	
	if(l!=maxlen) return;
	for(i=0;i<top;i++)
		if(strcmp(cur,ans[i])==0) return ;
	strcpy(ans[top++],cur);
}

int cmp(const void*a,const void*b)
{ return strcmp((char*)a,(char*)b); }

void backtrack(int i,int j,int l)
{
	if(i>len2 || j>len1)
	{ cur[l] = 0; add(l); return ; }
	if(str2[i]==str1[j])
	{
		cur[l] =  str2[i];
		backtrack(i+1,j+1,l+1);
	}
	else
	{
		backtrack(i+1,j,l);
		backtrack(i,j+1,l);
	}
}

void save()
{
	int i,j;
	for(i=1;i<=len2;i++)
		for(j=1;j<=len1;j++)
		{
			if((len[i][j]==len[i-1][j-1]+1) && (str2[i]==str1[j]))
			{
				s[tops].i = i; s[tops].j = j; s[tops++].len = len[i][j];
			}
		}
}

int cmp2(const void*a,const void*b)
{ return (*(node*)a).len-(*(node*)b).len; }

void add2()
{
	int i;
	for(i=1;i<=maxlen;i++)
		cur[i-1] = str2[path[i].i];
	cur[maxlen] = 0;
//	for(i=0;i<top;i++) if(strcmp(cur,ans[i])==0) return ;
	strcpy(ans[top++],cur);
}

void dfs(int len)//len,&sup3;¤&para;&Egrave;
{
	int i;
	if(len>maxlen)
	{ cur[len] = 0; add2(); return ;}
	for(i=start[len];s[i].len==len;i++)
	{
		if(s[i].i>path[len-1].i && s[i].j>path[len-1].j)
		{ path[len] = s[i]; dfs(len+1); }
	}
}

void find()
{
	int i,j;

	tops = 0;
	save();
	qsort(s,tops,sizeof(s[0]),cmp2);
	for(start[0]=0,i=1;i<=maxlen;i++)
	{
		for(j=start[i-1]+1;s[j].len!=i;j++);
		start[i] = j;
	}
	path[0].i = 0;
	path[0].j = 0;
	dfs(1);
}

void solve()
{
	int i,j;
	
	len1 = strlen(str1+1);
	len2 = strlen(str2+1);
	for(i=1;i<=len2;i++)
		for(j=1;j<=len1;j++)
		{
			if(str2[i]==str1[j]) len[i][j] = len[i-1][j-1]+1;
			else len[i][j] = (len[i][j-1]>len[i-1][j])?len[i][j-1]:len[i-1][j];
		}
	maxlen = len[len2][len1];
//	print();
	top = 0;
	find();
//	backtrack(1,1,0);
	qsort(ans,top,sizeof(ans[0]),cmp);
	printf("%s\n",ans[0]);
	for(i=1;i<top;i++)
	{
		if(strcmp(ans[i-1],ans[i])==0) continue;
		printf("%s\n",ans[i]);
	}
}

int main()
{
//	if(!freopen("1934.in","r",stdin)) return 12;
//	if(!freopen("19342.out","w",stdout)) return 12;

//	while(scanf("%s%s",str1+1,str2+1)!=EOF)
	scanf("%s%s",str1+1,str2+1);
	solve();
	return 123;
}

• 2个串全是30个a试试。 (0) lympanda 2004-10-20 23:30:41
• 搜索过程中要判重 (0) xiaomi 2004-10-21 00:53:07
  • 谢谢大大们提醒。 (0) gmds 2004-10-21 08:17:16