PKU 1458-Common Subsequence

問題概要

空白を含まない文字列2つがいくつかの空白に区切られて与えられる．
これらの最大共通部分列の長さを求めよ．

解法

文字列の長さ等の情報が読み取れなかったので適当に長さを1000文字程度だとする．
後は普通に最大共通部分列を求める．

実装(C++)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[1001][1001];
#define REP(i,x) for(int i=0;i<(int)(x);i++)
int main() {
	string a,b;
	for(;cin>>a>>b;){
		int as=a.size(),bs=b.size();
		memset(dp,0,sizeof(dp));
		REP(i,as)REP(j,bs){
			if(a[i]==b[j]){
				dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
				dp[as][bs]=max(dp[as][bs],dp[i+1][j+1]);
			}
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
			dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
		}
		cout<<dp[as][bs]<<endl;
	}
	return 0;
}