POJ 2250 - Compromise

http://poj.org/problem?id=2250

概要

2つの単語の列が与えられるので，それらの最長共通部分列を答える．

制約

解法

LCS の DP + 経路復元．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 using namespace std;
 5 
 6 struct renamer
 7 {
 8   map<string,int> m;
 9   vector<string> v;
10   int encode(const string& s)
11   {
12     map<string,int>::const_iterator it = m.find(s);
13     if (it == m.end()) {
14       const int id = m.size();
15       m.insert(make_pair(s, id));
16       v.push_back(s);
17       return id;
18     } else {
19       return it->second;
20     }
21   }
22   string decode(int id) const { return v[id]; }
23 };
24 
25 int main()
26 {
27   ios::sync_with_stdio(false);
28   string s;
29   while (cin >> s) {
30     vector<int> xs, ys;
31     renamer r;
32     xs.push_back(r.encode(s));
33     while (cin >> s && s != "#") {
34       xs.push_back(r.encode(s));
35     }
36     while (cin >> s && s != "#") {
37       ys.push_back(r.encode(s));
38     }
39 
40     const int N = xs.size(), M = ys.size();
41     vector<vector<int> > lcs(N+1, vector<int>(M+1, 0));
42     vector<vector<pair<int,int> > > prev(N+1, vector<pair<int,int> >(M+1, make_pair(-1, -1)));
43     for (int i = 1; i <= N; i++) {
44       for (int j = 1; j <= M; j++) {
45         int t = lcs[i-1][j-1] + (xs[i-1] == ys[j-1]);
46         lcs[i][j] = max(t, max(lcs[i-1][j], lcs[i][j-1]));
47         if (lcs[i][j] == t) {
48           prev[i][j] = make_pair(i-1, j-1);
49         } else if (lcs[i][j] == lcs[i-1][j]) {
50           prev[i][j] = make_pair(i-1, j);
51         } else {
52           prev[i][j] = make_pair(i, j-1);
53         }
54       }
55     }
56 
57     vector<int> seq;
58     for (int i = N, j = M;;) {
59       const int k = prev[i][j].first;
60       const int l = prev[i][j].second;
61       if (k == -1 || l == -1) {
62         break;
63       }
64       if (k+1 == i && l+1 == j && lcs[k][l]+1 == lcs[i][j]) {
65         seq.push_back(xs[i-1]);
66       }
67       i = k;
68       j = l;
69     }
70     for (vector<int>::const_reverse_iterator it = seq.rbegin(); it != seq.rend(); ++it) {
71       if (it != seq.rbegin()) {
72         cout << ' ';
73       }
74       cout << r.decode(*it);
75     }
76     cout << endl;
77   }
78   return 0;
79 }
poj/2250.cc