[UVA] 531 - Compromise

題意:
輸入兩個字串，輸出最長共同子序列(Longest Common Subsequence)。

最長共同子序列就是指兩序列在相同順序下的相同元素，不一定要連續!
舉個例子，
1 2 3 5 7 6
1 3 6 5 7
最長共同子序列就是:
1 3 5 7

1 3 5 7是兩個序列的相同元素，而且都以相同順序出現 1->3->5->7，
像是 1 3 5 6 就不是，因為第二個序列找不到依序出現1 3 5 6的

這一題就是把數字換成字串去找LCS而已。

---------------------------------------------

方法:
動態規劃，以先前已經計算好的結果來做下一次的計算，
我先做預處理，將字串先以數字代替，以加快之後在字串上的比較。
我這裡將到目前為止最長的子序列以vector存取，
所以最後直接輸出最後一個vector，
但是其實每計算一次就複製一個vector效率並不高。

在計算過程做標記，最後再循著標記走回來輸出也是一個方法。

Longest Common Subsequence: Dynamic Programming
這個網站寫的蠻好懂得可以參考看看!

---------------------------------------------

/* 20150825
 * hanting
 * UVa 531 - Compromise
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <cstring>//memset
using namespace std;
map<string,int> id;
vector<string> store;
int ID(string str)
{
    if(id.count(str)) return id[str];
    else
    {
        store.push_back(str);
        return id[str]=store.size()-1;
    }
}
bool input(vector<int> &a,vector<int> &b)
{
    a.resize(1);
    b.resize(1);

    string str;
    bool chk=false;
    while(cin>>str and str!="#")
    {
        chk=true;
        a.push_back(ID(str));
    }

    while(cin>>str and str!="#")
    {
        b.push_back(ID(str));
    }
    return chk;
}
vector<int> operator+(vector<int>& vec,int c)
{
    vec.push_back(c);
    return vec;
}
vector<int> Max(vector<int> &a,vector<int> &b)
{
    return a.size()>b.size() ? a : b;
}
int main()
{
    vector<int> a,b;
    while(input(a,b))
    {
        vector<int> LCS[a.size()+1][b.size()+1];
        for(int i=1;i<a.size();i++)
        {
            for(int j=1;j<b.size();j++)
            {
                if(a[i]==b[j])
                {
                    LCS[i][j]=LCS[i-1][j-1]+a[i];
                }
                else
                {
                    LCS[i][j]=Max(LCS[i-1][j],LCS[i][j-1]);
                }
            }
        }
        vector<int> ans=LCS[a.size()-1][b.size()-1];
        for(int i=0;i<ans.size()-1;i++)
        {
            int t=ans[i];
            cout<<store[t]<<" ";
        }
        cout<<store[ans.back()]<<endl;
    }
    return 0;
}