LCS

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

struct Node {
    int size;
    Node * link;
    map<char, Node*> next;

    Node() : size(0), link(nullptr) {}
};

class SA{
    vector<Node*> first;

public:
    SA(string s) : first(1, new Node()) {
        Node * last = first[0];
        for (const char& c : s) {
            Node * _new = new Node();
            first.emplace_back(_new);
            _new->size = last->size + 1;
            Node * i = last;
            while (i != nullptr && !i->next.count(c)) {
                i->next[c] = _new;
                i = i->link;
            }
            if (i == nullptr) {
                _new->link = first[0];
            } else {
                Node * other = i->next[c];
                if (i->size + 1 == other->size) {
                    _new->link = other;
                } else {
                    Node * __new = new Node();
                    first.emplace_back(__new);
                    __new->size = i->size + 1;
                    __new->next = other->next;
                    __new->link = other->link;
                    while (i != nullptr && i->next[c] == other) {
                        i->next[c] = __new;
                        i = i->link;
                    }
                    other->link = _new->link = __new;
                }
            }
            last = _new;
        }
    }

    string lcs(string other) {
        Node * v = first[0];
        unsigned long l = 0, best = 0, bestpos = 0;
        for (unsigned long i = 0; i < other.length(); ++i) {
            char c = other[i];
            while (v != first[0] && !v->next.count(c)) {
                v = v->link;
                l = v->size;
            }
            if (v->next.count(c)) {
                v = v->next[c];
                ++l;
            }
            if (l > best) {
                best = l;
                bestpos = i;
            }
        }
        return other.substr(bestpos - best + 1, best);
    }

    ~SA() {
        for (auto ptr : first) {
            delete ptr;
        }
    }
};

void solution() {
    string s1, s2;
    cin >> s1 >> s2;
    SA sa(s1);
    cout << sa.lcs(s2) << '\n';
}

int main()
{
    iostream::sync_with_stdio(false);
    solution();
    return 0;
}