[UVa Online Judge] 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 i = 1; i <= m; i++) {
11         if (s[i - 1] == t[0]) cur[i] = 1;
12         else cur[i] = cur[i - 1];
13     }
14     for (int j = 1; j < n; j++) {
15         int pre = 0;
16         for (int i = 1; i <= m; i++) {
17             int temp = cur[i];
18             if (s[i - 1] == t[j]) cur[i] = pre + 1;
19             else cur[i] = max(cur[i], cur[i - 1]);
20             pre = temp;
21         }
22     }
23     return cur[m];
24 }
25 
26 int main(void) {
27     string s, t;
28     while (getline(cin, s)) {
29         getline(cin, t);
30         cout << lcs(s, t) << endl;
31     }
32     return 0;
33 }