2010年西北工业大学机试第五题

第一个样例是abfc

第二个样例是on

#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int num[1005][1005] = {0};
int main(){
	
	string a,b;
	while(cin>>a>>b){
	//	cout<<a<<" "<<b<<endl;
		for(int i = 1;i <= a.length();i++){
			for(int j = 1;j <= b.length();j++){
				if(a[i-1] == b[j-1]){
					num[i][j] = num[i-1][j-1]+1;
				}else{
					num[i][j] = max(num[i-1][j],num[i][j-1]);
					num[i][j] = max(num[i][j],num[i-1][j-1]);
				}
			}
		}
		cout<<num[a.length()][b.length()]<<endl;
	}
	
	return 0;
}