cpp1.cpp

经典的计算最长公子序列

#include<stdio.h>
#include<string.h>
#define STRMAX 300

int length1,length2,max;
char str1[STRMAX],str2[STRMAX];

void search(int,int,int);

void main()
{
	int tempLength;
	char tempStr[STRMAX];

	while (scanf("%s%s",str1,str2) != EOF)
	{
		max = 0;
		length1 = strlen(str1);
		length2 = strlen(str2);
	
		if (length1 > length2)//keep str1 is shorter than str2
		{
			tempLength = length1;
			length1 = length2;
			length2 = tempLength;

			strcpy(tempStr,str1);
			strcpy(str1,str2);
			strcpy(str2,tempStr);
		}


		search(0,0,0);//search from str1[0],str2[0] and starting from 0 shared elements already
		printf("%d\n",max);
	}
}

void search(int a,int b,int c)//search from str1[a],str2[b] and there already c shared elements
{
	int i,j;
	for (i = a ; i < length1 ; i++ )//str1
	{
		for (j = b ; j < length2 ; j++)//str2
		{
			if (str1[i] == str2[j])
			{
				if (a != length1)
				{
					search(i+1,j+1,c+1);
					goto end;
				}
				search(i+1,j+1,c+1);
				break;
			}
		}
	}

	if (i == length1)//end of loop
	{
		max = (max > c ? max : c);
	}
end:;
}