test/src/string/compare_substring/abc141_e.test.cpp

• View this file on GitHub
• Last update: 2022-05-29 02:48:02+09:00
• Problem: https://atcoder.jp/contests/abc141/tasks/abc141_e

Depends on

• Sparse Table (library/datastructure/sparse_table.hpp)
• Compare Substring (library/string/compare_substring.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc141/tasks/abc141_e"

#include <iostream>
#include <map>

#include "library/string/compare_substring.hpp"

int main() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    suisen::CompareSubstring cmp(s);
    using Substring = decltype(cmp.substr(0, 0));
    
    auto is_ok = [&](int w) {
        std::map<Substring, int> st;
        for (int i = 0; i + w <= n; ++i) {
            Substring sub = cmp.substr(i, i + w);
            if (auto it = st.find(sub); it != st.end()) {
                if (it->second + w <= i) return true;
            } else {
                st[sub] = i;
            }
        }
        return false;
    };

    int l = 0, r = n / 2 + 1;
    while (r - l > 1) {
        int w = (l + r) >> 1;
        (is_ok(w) ? l : r) = w;
    }
    std::cout << l << std::endl;
    
    return 0;
}

#line 1 "test/src/string/compare_substring/abc141_e.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc141/tasks/abc141_e"

#include <iostream>
#include <map>

#line 1 "library/string/compare_substring.hpp"



#include <atcoder/segtree>
#include <atcoder/string>

#line 1 "library/datastructure/sparse_table.hpp"



#include <vector>

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct SparseTable {
        SparseTable() = default;
        SparseTable(std::vector<T>&& a) : n(a.size()), log(floor_log2(n)), table(log + 1), flog(n + 1, 0) {
            build_table(std::move(a));
            build_flog_table();
        }
        SparseTable(const std::vector<T>& a) : SparseTable(std::vector<T>(a)) {}
        T operator()(int l, int r) const {
            if (l >= r) return e();
            int i = flog[r - l];
            return op(table[i][l], table[i][r - (1 << i)]);
        }
        T prod(int l, int r) const {
            return (*this)(l, r);
        }
    private:
        int n;
        int log;
        std::vector<std::vector<T>> table;
        std::vector<int> flog;

        void build_table(std::vector<T>&& a) {
            table[0] = std::move(a);
            for (int i = 0; i < log; ++i) {
                int lmax = n - (1 << (i + 1));
                table[i + 1].resize(lmax + 1);
                for (int l = 0; l <= lmax; ++l) table[i + 1][l] = op(table[i][l], table[i][l + (1 << i)]);
            }
        }
        void build_flog_table() {
            for (int l = 0; l < log; ++l) {
                std::fill(flog.begin() + (1 << l), flog.begin() + (1 << (l + 1)), l);
            }
            std::fill(flog.begin() + (1 << log), flog.end(), log);
        }
        static int floor_log2(int i) {
            return 31 - __builtin_clz(i);
        }
    };
} // namespace suisen


#line 8 "library/string/compare_substring.hpp"

namespace suisen {
    namespace internal::compare_substring {
        constexpr int op(int x, int y) { return std::min(x, y); }
        constexpr int e() { return std::numeric_limits<int>::max(); }
    }
    namespace compare_substring_rmq {
        using SegmentTreeRmQ = atcoder::segtree<int, internal::compare_substring::op, internal::compare_substring::e>;
        using SparseTableRmQ = SparseTable<int, internal::compare_substring::op, internal::compare_substring::e>;
    }
    template <typename RmQ = compare_substring_rmq::SparseTableRmQ>
    struct CompareSubstring {
        CompareSubstring() = default;
        CompareSubstring(const std::vector<int> &sa, const std::vector<int> &lcp) : _n(sa.size()), _sa_inv(_n), _lcp_min(lcp) {
            for (int i = 0; i < _n; ++i) _sa_inv[sa[i]] = i;
        }
        template <typename T>
        CompareSubstring(const std::vector<T> &s) : CompareSubstring(s, atcoder::suffix_array(s), DUMMY_PARAMETER) {}
        template <typename T>
        CompareSubstring(const std::vector<T> &s, const T& upper) : CompareSubstring(s, atcoder::suffix_array(s, upper), DUMMY_PARAMETER) {}
        CompareSubstring(const std::string &s) : CompareSubstring(s, atcoder::suffix_array(s), DUMMY_PARAMETER) {}

        int lcp(int l1, int r1, int l2, int r2) const {
            assert(0 <= l1 and l1 <= r1 and r1 <= _n);
            assert(0 <= l2 and l2 <= r2 and r2 <= _n);
            if (l1 == r1 or l2 == r2) return 0;
            auto [i1, i2] = std::minmax(_sa_inv[l1], _sa_inv[l2]);
            return std::min(std::min(r1 - l1, r2 - l2), _lcp_min(i1, i2));
        }
        int compare(int l1, int r1, int l2, int r2) const {
            const int len = lcp(l1, r1, l2, r2);
            const int w1 = r1 - l1, w2 = r2 - l2;
            return len == w1 and len == w2 ? 0 : len == w1 ? -1 : len == w2 ? 1 : _sa_inv[l1 + len] < _sa_inv[l2 + len] ? -1 : 1;
        }
        int operator()(int l1, int r1, int l2, int r2) const {
            return compare(l1, r1, l2, r2);
        }

        int lcp(const std::pair<int, int> &seg1, const std::pair<int, int> &seg2) const {
            return lcp(seg1.first, seg1.second, seg2.first, seg2.second);
        }
        int compare(const std::pair<int, int> &seg1, const std::pair<int, int> &seg2) const {
            return compare(seg1.first, seg1.second, seg2.first, seg2.second);
        }
        int operator()(const std::pair<int, int> &seg1, const std::pair<int, int> &seg2) const {
            return compare(seg1, seg2);
        }

        struct Substring {
            int l, r;
            Substring() = default;
            Substring(int l, int r, CompareSubstring<RmQ> const * ptr) : l(l), r(r), _ptr(ptr) {}

            int size() const { return r - l; }

            int lcp(const Substring &rhs) const {
                return _ptr->lcp(l, r, rhs.l, rhs.r);
            }
            int compare(const Substring &rhs) const {
                assert(rhs._ptr == _ptr);
                return _ptr->compare(l, r, rhs.l, rhs.r);
            }
            bool operator==(const Substring &rhs) const { return compare(rhs) == 0; }
            bool operator!=(const Substring &rhs) const { return compare(rhs) != 0; }
            bool operator< (const Substring &rhs) const { return compare(rhs) <  0; }
            bool operator<=(const Substring &rhs) const { return compare(rhs) <= 0; }
            bool operator> (const Substring &rhs) const { return compare(rhs) >  0; }
            bool operator>=(const Substring &rhs) const { return compare(rhs) >= 0; }
        private:
            CompareSubstring<RmQ> const * _ptr;
        };

        Substring substr(int l, int r) const { return Substring(l, r, this); }
        Substring substr(const std::pair<int, int> &seg) const { return substr(seg.first, seg.second); }
    private:
        static constexpr bool DUMMY_PARAMETER{};
        int _n;
        std::vector<int> _sa_inv;
        RmQ _lcp_min;

        template <typename Container>
        CompareSubstring(const Container &s, const std::vector<int> &sa, bool) : CompareSubstring(sa, atcoder::lcp_array(s, sa)) {}
    };
} // namespace suisen


#line 7 "test/src/string/compare_substring/abc141_e.test.cpp"

int main() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    suisen::CompareSubstring cmp(s);
    using Substring = decltype(cmp.substr(0, 0));
    
    auto is_ok = [&](int w) {
        std::map<Substring, int> st;
        for (int i = 0; i + w <= n; ++i) {
            Substring sub = cmp.substr(i, i + w);
            if (auto it = st.find(sub); it != st.end()) {
                if (it->second + w <= i) return true;
            } else {
                st[sub] = i;
            }
        }
        return false;
    };

    int l = 0, r = n / 2 + 1;
    while (r - l > 1) {
        int w = (l + r) >> 1;
        (is_ok(w) ? l : r) = w;
    }
    std::cout << l << std::endl;
    
    return 0;
}

Back to top page