最长公共子序列
题目链接:POJ 1458
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> using namespace std; string s1,s2; int a[1005][1005]; int main () { while(cin >> s1 >> s2) { int len1=s1.length(); int len2=s2.length(); for (int i=1;i<=len1;i++) { for (int j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1]) a[i][j]=a[i-1][j-1]+1; else a[i][j]=max(a[i-1][j],a[i][j-1]); } } cout << a[len1][len2] << endl; } return 0; }