Function MakeLCS

library/cpp/lcs/lcs_via_lis.h:61–160

        template <typename TVal, typename TSequence, typename TResult>
        size_t MakeLCS(TSequence s1, TSequence s2, TResult* res = nullptr, TLCSCtx<TVal>* ctx = nullptr) {
            typedef TLCSCtx<TVal> TCtx;

            THolder<TCtx> ctxhld;

            if (!ctx) {
                ctxhld.Reset(new TCtx());
                ctx = ctxhld.Get();
            } else {
                ctx->Reset();
            }

            size_t maxsize = Max(s1.Size, s2.Size);
            auto& index = *(ctx->Encounters);

            for (auto it = s1.Begin; it != s1.End; ++it) {
                index[*it];
            }

            for (auto it = s2.Begin; it != s2.End; ++it) {
                auto hit = index.find(*it);

                if (hit != index.end()) {
                    hit->second.push_back(it - s2.Begin);
                }
            }

            if (!res) {
                auto& lastindex = ctx->ResultBuffer;
                lastindex.reserve(maxsize);

                for (auto it1 = s1.Begin; it1 != s1.End; ++it1) {
                    const auto& sub2 = index[*it1];

                    for (auto it2 = sub2.rbegin(); it2 != sub2.rend(); ++it2) {
                        ui32 x = *it2;

                        auto lit = LowerBound(lastindex.begin(), lastindex.end(), x);

                        if (lit == lastindex.end()) {
                            lastindex.push_back(x);
                        } else {
                            *lit = x;
                        }
                    }
                }

                return lastindex.size();
            } else {
                auto& lastindex = ctx->LastIndex;
                auto& cover = ctx->Cover;

                lastindex.reserve(maxsize);

                for (auto it1 = s1.Begin; it1 != s1.End; ++it1) {
                    const auto& sub2 = index[*it1];

                    for (auto it2 = sub2.rbegin(); it2 != sub2.rend(); ++it2) {