lcs.cpp

#include <deque>
#include <set>
#include <memory>
#include <algorithm>
#include <functional>

struct weight_dir{
    enum{
        left, up, bi, next,
    } dir;
    int weight;
};

template<class T>
std::set<std::deque<T>> lcs(const std::deque<T> &x, const std::deque<T> &y){
    std::set<std::deque<T>> result;
    std::size_t x_length = x.size() + 1, y_length = y.size() + 1;
    std::unique_ptr<weight_dir, std::default_delete<weight_dir>> table(new weight_dir[x_length * y_length]);
    auto acc = [&](std::size_t xn, std::size_t yn) -> weight_dir&{
        return table.get()[yn * x_length + xn];
    };
    for(std::size_t i = 0; i < x_length; ++i){
        acc(i, 0).weight = 0;
    }
    for(std::size_t i = 0; i < y_length; ++i){
        acc(0, i).weight = 0;
    }
    for(std::size_t i = 1; i < x_length; ++i){
        for(std::size_t j = 1; j < y_length; ++j){
            if(x[i - 1] == y[j - 1]){
                acc(i, j).weight = acc(i - 1, j - 1).weight + 1;
                acc(i, j).dir = weight_dir::next;
            }else{
                const weight_dir &s = acc(i - 1, j), t = acc(i, j - 1);
                if(s.weight > t.weight){
                    acc(i, j).weight = s.weight;
                    acc(i, j).dir = weight_dir::up;
                }else if(s.weight < t.weight){
                    acc(i, j).weight = t.weight;
                    acc(i, j).dir = weight_dir::left;
                }else{
                    acc(i, j).weight = s.weight;
                    acc(i, j).dir = weight_dir::bi;
                }
            }
        }
    }
    std::function<void(std::size_t, std::size_t, std::deque<T>&)> make_result;
    make_result = [&](std::size_t i, std::size_t j, std::deque<T> &seq) -> void{
        weight_dir &item = acc(i, j);
        if(i == 0 || j == 0){
            result.insert(seq);
            return;
        }else if(item.dir == weight_dir::next){
            seq.push_front(x[i - 1]);
            make_result(i - 1, j - 1, seq);
            seq.pop_front();
        }else if(item.dir == weight_dir::up){
            make_result(i - 1, j, seq);
        }else if(item.dir == weight_dir::left){
            make_result(i, j - 1, seq);
        }else if(item.dir == weight_dir::bi){
            make_result(i - 1, j, seq);
            make_result(i, j - 1, seq);
        }
    };
    {
        std::deque<T> seq;
        make_result(x_length - 1, y_length - 1, seq);
    }
    return result;
}

int main(int argc, char *argv[]){
    std::deque<char> x, y;
    std::set<std::deque<char>> result;
    
    x.push_back('A');
    x.push_back('B');
    x.push_back('C');
    x.push_back('B');
    x.push_back('D');
    x.push_back('A');
    x.push_back('B');

    y.push_back('B');
    y.push_back('D');
    y.push_back('C');
    y.push_back('A');
    y.push_back('B');
    y.push_back('A');

    result = lcs(x, y);
    return 0;
}