[UVa OJ] Longest Common Subsequence

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 int lcs(string s, string t) {
 8     int m = s.length(), n = t.length();
 9     vector<int> cur(m + 1, 0);
10     for (int j = 1; j <= n; j++) {
11         int pre = 0;
12         for (int i = 1; i <= m; i++) {
13             int temp = cur[i];
14             cur[i] = (s[i - 1] == t[j - 1] ? pre + 1 : max(cur[i], cur[i - 1]));
15             pre = temp;
16         }
17     }
18     return cur[m];
19 }
20 
21 int main(void) {
22     string s, t;
23     while (getline(cin, s)) {
24         getline(cin, t);
25         printf("%d\n", lcs(s, t));
26     }
27     return 0;
28 }