Longest Common Subsequence implementation

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <ctime>
#include <cstdlib>
#include <boost/smart_ptr.hpp>
#include <boost/cstdint.hpp>

template <typename Iterator>
size_t generalized_hash(Iterator begin, const Iterator &end){
    size_t ret = 0xF00BA8;
    const size_t factor =
#ifdef _M_X64
        0x8BADF00DDEADBEEF;
#else
        0xDEADBEEF;
#endif
    for (; begin != end; ++begin){
        ret *= factor;
        ret ^= *begin;
    }
    return ret;
}

size_t hash_string(const std::string &s){
    return generalized_hash(s.begin(), s.end());
}


class fast_string{
    std::string s;
    size_t hash;
    int unique;
public:
    fast_string(const std::string &s): s(), hash(hash_string(s)), unique(0){}
    fast_string(const fast_string &fs): s(fs.s), hash(fs.hash), unique(fs.unique){}
    bool operator==(const fast_string &s) const{
        return !(this->s != s.s);
    }
    bool operator!=(const fast_string &s) const{
        return this->hash != s.hash || this->s != s.s;
    }
    const std::string &get_string() const{
        return this->s;
    }
    void set_unique(int where){
        this->unique = where;
    }
    int get_unique() const{
        return this->unique;
    }
    operator size_t() const{
        return this->hash;
    }
};

template <typename T>
class generalized_set{
    typedef typename std::vector<T>::const_iterator it_t;
    it_t begin, end;
    size_t hash;
    int unique;
public:
    generalized_set(const it_t &begin, const it_t &end): begin(begin), end(end), hash(generalized_hash(begin, end)), unique(0){}
    generalized_set(const generalized_set &gs): begin(gs.begin), end(gs.end), hash(gs.hash), unique(gs.unique){}
    bool operator==(const generalized_set<T> &gs) const{
        return !(*this != gs);
    }
    bool operator!=(const generalized_set<T> &gs) const{
        if (this->hash != gs.hash)
            return 1;
        auto i = this->begin, j = gs.begin;
        for (; i != this->end && j != gs.end; ++i, ++j){
            if (*i != *j)
                return 1;
        }
        return i == this->end || j == gs.end;
    }
    void set_unique(int where){
        this->unique = where;
    }
    int get_unique() const{
        return this->unique;
    }
};

typedef std::pair<int, int> key_t;

struct coord{
    int x, y;
    coord(): x(0), y(0){}
};

class lcs_result;

typedef boost::shared_ptr<lcs_result> ptr;

#ifdef _DEBUG
#define vassert(x) if (!(x)) __debugbreak()
#else
#define vassert
#endif

class lcs_result{
    ptr child;
public:
    void set_child(const ptr &p){
        int d = -1;
        bool goal;
        if (p){
            d = p->distance;
            goal = p->goal;
        }
        this->child = p;
        if (d >= 0){
            this->distance = d + 1;
            this->goal = goal;
        }
    }
    ptr get_child(){
        return this->child;
    }
    enum Arrow{
        UP_LEFT,
        LEFT,
        UP,
        ANY
    };
    Arrow type;
    int length;
    int distance;
    bool goal;
    coord initial,
        final;
    static volatile unsigned long long live_instances;
    lcs_result(): type(ANY), length(0), distance(0), goal(0){
        this->live_instances++;
    }
    ~lcs_result(){
        //vassert(!(!this->initial.x && !this->initial.y));
        this->live_instances--;
        std::vector<ptr> v;
        ptr p = this->child;
        this->child.reset();
        while (p){
            vassert(p.use_count() >= 1);
            if (p.use_count() > 1)
                break;
            v.push_back(p);
            auto copy = p->child;
            p->child.reset();
            p = copy;
        }
    }
    void set_coord(int x, int y){
        this->initial.x = x;
        this->initial.y = y;
        this->final.x = x;
        this->final.y = y;
        if (!x && !y)
            this->goal = 1;
    }
    bool try_merge(){
        if (!this->child)
            return 0;
        if (this->type != this->child->type)
            return 0;
        if (this->child.use_count() > 1)
            return 0;
        this->initial = this->child->initial;
        if (this->type == UP_LEFT)
            this->length++;
        this->set_child(this->child->child);
        return 1;
    }
    bool operator<(const lcs_result &b) const{
        if (this->length < b.length)
            return 1;
        //if (this->distance > b.distance)
        //  return 1;
        //if (!this->goal && b.goal)
        //  return 1;
        return 0;
    }
    bool operator>(const lcs_result &b) const{
        return b < *this;
    }
};

volatile unsigned long long lcs_result::live_instances = 0;

typedef std::map<std::pair<int, int>, lcs_result> table_t;

template <typename T>
lcs_result *lcs_b(const std::vector<T> &x, const std::vector<T> &y, int i, int j, ptr up, ptr left, ptr up_left){
    auto res = new lcs_result;
    if (i < 0 || j < 0){
        res->type = lcs_result::LEFT;
        res->length = 0;
        res->set_coord(i, j);
        return res;
    }
    if (x[i] == y[j]){
        res->type = lcs_result::UP_LEFT;
        res->set_child(up_left);
        res->length = (up_left ? up_left->length : 0) + 1;
    }else{
        ptr a = left;
        ptr b = up;
        if (!left && !up){
            res->type = lcs_result::LEFT;
            res->length = 0;
        }else{
            if (left && (!up || up && *left > *up)){
                res->type = lcs_result::LEFT;
                res->set_child(left);
                res->length = left->length;
            }else if (up && (!left || left && *left < *up)){
                res->type = lcs_result::UP;
                res->set_child(up);
                res->length = up->length;
            }else{
                res->length = left->length;
                res->set_child(left);
                res->type = lcs_result::LEFT;
            }
        }
    }
    res->set_coord(i, j);
    return res;
}

template <typename T>
T deref(std::vector<T> *v, int index){
    if (index < 0 || (size_t)index >= v->size())
        return T();
    return (*v)[index];
}

template <typename T>
ptr lcs_length(const std::vector<T> &x, const std::vector<T> &y){
    //std::map<std::pair<int, int>, lcs_result> table;
    int h = y.size();
    int w = x.size();
    int x0 = 0;
    int y1 = 0;
    auto stack0 = new std::vector<ptr>,
        last_stack0 = new std::vector<ptr>,
        stack1 = new std::vector<ptr>,
        last_stack1 = new std::vector<ptr>;
    for (int i = 1;;){
        bool any = 0;
        /*
        if (i == 23){
            for (size_t i = 0; i < stack0->size(); i++){
                auto p = (*stack0)[i];
                for (auto p2 = p; p2; p2 = p2->get_child()){
                    if (!p2->initial.x && !p2->initial.y)
                        __debugbreak();
                }
            }
        }
        */
        stack0->clear();
        stack0->reserve(i / 2);
        for (int y0 = 0; y0 < i / 2; y0++){
            if ((size_t)x0 >= x.size() || (size_t)y0 >= y.size())
                break;
            auto left = deref(last_stack0, y0);
            if (x0 - 1 == y0 && last_stack1->size()){
                left = last_stack1->back();
            }
            auto node = lcs_b(x, y , x0, y0, deref(stack0, y0 - 1), left, deref(last_stack0, y0 - 1));
            stack0->push_back(ptr(node));
            any = 1;
        }
        x0++;
        i++;
        stack1->clear();
        stack1->reserve(i / 2);
        for (int x1 = 0; x1 < i / 2; x1++){
            if ((size_t)x1 >= x.size() || (size_t)y1 >= y.size())
                break;
            auto up = deref(last_stack1, x1);
            if (x1 == y1 && stack0->size()){
                up = stack0->back();
            }
            auto node = lcs_b(x, y , x1, y1, up, deref(stack1, x1 - 1), deref(last_stack1, x1 - 1));
            stack1->push_back(ptr(node));
            any = 1;
        }
        y1++;
        i++;
        if (!any)
            break;
        for (auto p : *stack0){
            if (!p || !p->get_child())
                continue;
            p->get_child()->try_merge();
        }
        for (auto p : *stack1){
            if (!p || !p->get_child())
                continue;
            p->get_child()->try_merge();
        }
        std::swap(stack0, last_stack0);
        std::swap(stack1, last_stack1);
    }
    ptr res;
    if (last_stack0->size() > last_stack1->size())
        res = last_stack0->back();
    else
        res = last_stack1->back();
    last_stack0->clear();
    last_stack1->clear();
    for (ptr i = res; i; i = i->get_child())
        while (i->try_merge());
    /*
    for (ptr i = res; i; i = i->get_child()){
        switch (i->type){
            case lcs_result::LEFT:
            case lcs_result::ANY:
                std::cout <<"left";
                break;
            case lcs_result::UP:
                std::cout <<"up";
                break;
            case lcs_result::UP_LEFT:
                std::cout <<"up-left";
                break;
        }
        std::cout <<" ("<<i->initial.x<<"-"<<i->final.x<<", "<<i->initial.y<<"-"<<i->final.y<<")\n";
    }
    */
    return res;
}

template <typename T>
std::vector<T> lcs_b(const std::vector<T> &x, const std::vector<T> &y, int i, int j, ptr lookup){
    std::vector<T> ret;
    assert(lookup->final.x == i && lookup->final.y == j);
    while (i >= 0 && j >= 0){
        switch (lookup->type){
            case lcs_result::LEFT:
                while (i >= lookup->initial.x){
                    T insert = x[i];
                    insert.set_unique(-1);
                    ret.push_back(insert);
                    i--;
                }
                break;
            case lcs_result::UP:
                while (j >= lookup->initial.y){
                    T insert = y[j];
                    insert.set_unique(1);
                    ret.push_back(insert);
                    j--;
                }
                break;
            case lcs_result::UP_LEFT:
                while (i >= lookup->initial.x){
                    ret.push_back(x[i]);
                    i--;
                    j--;
                }
                break;
            default:
                assert(0);
        }
        lookup = lookup->get_child();
    }
    while (j >= 0){
        T insert = y[j];
        insert.set_unique(1);
        ret.push_back(insert);
        j--;
    }
    while (i >= 0){
        T insert = x[i];
        insert.set_unique(-1);
        ret.push_back(insert);
        i--;
    }
    std::reverse(ret.begin(), ret.end());
    return ret;
}

template <typename T>
std::vector<T> lcs_b(const std::vector<T> &x, const std::vector<T> &y){
    auto lcs_lookup = lcs_length(x, y);
    return lcs_b(x, y, x.size() - 1, y.size() - 1, lcs_lookup);
}

std::vector<fast_string> read_file(const char *path){
    std::ifstream file(path);
    std::vector<fast_string> ret;
    ret.reserve(150000);
    while (1){
        std::string line;
        std::getline(file, line);
        if (!file)
            break;
        ret.push_back(line);
    }
    for (int i = ret.size(); ret.size() < 150000; i++)
        ret.push_back(ret[((size_t)pow(i, 3.14159265)) % ret.size()]);
    return ret;
}

template <typename T>
std::vector<generalized_set<T> > split_vector(const std::vector<T> &v){
    std::vector<generalized_set<T> > ret;
    auto last = v.begin();
    const size_t split_size = 64;
    for (size_t i = 0; ; i += split_size){
        if (i + split_size > v.size()){
            ret.push_back(generalized_set<T>(last, v.end()));
            break;
        }
        auto first = last;
        last += split_size;
        ret.push_back(generalized_set<T>(first, last));
    }
    return ret;
}

int main(){
    std::vector<fast_string> string0 = read_file("0.txt"),
        string1 = read_file("1.txt");
    auto v0 = split_vector(string0);
    auto v1 = split_vector(string1);
    for (const auto l : lcs_b(v0, v1)){
        int unique = l.get_unique();
        if (unique < 0)
            std::cout <<"(<=)\n";
        else if (unique > 0)
            std::cout <<"(=>)\n";
        else
            std::cout <<"(==)\n";
        //std::cout <<l.get_string()<<std::endl;
    }
}