1458.txt

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

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

int ans[1000][1000];
char route1[1001],route2[1001];
int n,m;

void doit()
{
	int i,j;
	for( i=0; i<=n; i++)
		ans[i][0] = 0;
	for( j=0; j<=m; j++)
		ans[0][j] = 0;

	for( i=1; i<=n; i++ )
	for( j=1; j<=m; j++ )
	{
		if( route1[i] == route2[j] )
		{
			ans[i][j] = ans[i-1][j-1] + 1;
		}
		else ans[i][j] = -1;

		if( ans[i-1][j] > ans[i][j] )
			ans[i][j] = ans[i-1][j];

		if( ans[i][j-1] > ans[i][j] )
			ans[i][j] = ans[i][j-1];
	}
}


int main()
{

	while( scanf("%s%s",route1+1,route2+1) == 2 )
	{
		n = strlen( route1+1 );
		m = strlen( route2+1 );

		doit();

		printf( "%d\n", ans[n][m] );
	}

	return 0;
}