Editorial for Pondo Compare

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Build the suffix array of $s$ ~s~ by doubling: after $k$ ~k~ rounds, suffixes are ordered by their first $2^k$ ~2^k~ characters. Then compute the LCP array with Kasai's algorithm, and put it in a sparse table so any range minimum can be answered in $O(1)$ ~O(1)~.

The LCP of the suffixes starting at $i$ ~i~ and $j$ ~j~ is $n - i$ ~n - i~ if $i = j$ ~i = j~, and otherwise the minimum LCP-array value between their suffix-array ranks. For a query, let $\mathrm{len}_1 = r_1 - l_1 + 1$ ~\mathrm{len}_1 = r_1 - l_1 + 1~ and $\mathrm{len}_2 = r_2 - l_2 + 1$ ~\mathrm{len}_2 = r_2 - l_2 + 1~, and let $h$ ~h~ be the LCP of suffixes $l_1$ ~l_1~ and $l_2$ ~l_2~. If $h \ge \min(\mathrm{len}_1, \mathrm{len}_2)$ , one substring is a prefix of the other, so the shorter one is smaller (or they are equal). Otherwise they differ at offset $h$ ~h~, and it is enough to compare $s[l_1 + h]$ ~s[l_1 + h]~ with $s[l_2 + h]$ ~s[l_2 + h]~.

Building the suffix array takes $O(n \log^2 n)$ ~O(n \log^2 n)~, and answering all queries is $O(n + q)$ ~O(n + q)~.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    string s;
    cin >> n >> q >> s;

    vector<int> sa(n), rnk(n), tmp(n);
    for (int i = 0; i < n; ++i) {
        sa[i] = i;
        rnk[i] = int((unsigned char)s[i]);
    }
    for (int len = 1;; len <<= 1) {
        auto cmp = [&](int a, int b) {
            if (rnk[a] != rnk[b]) {
                return rnk[a] < rnk[b];
            }
            int ra = (a + len < n) ? rnk[a + len] : -1;
            int rb = (b + len < n) ? rnk[b + len] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; ++i) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        rnk.swap(tmp);
        if (rnk[sa[n - 1]] == n - 1) {
            break;
        }
        if (len >= n) {
            break;
        }
    }

    vector<int> lcp(max(n - 1, 0));
    int h = 0;
    for (int i = 0; i < n; ++i) {
        int r = rnk[i];
        if (r == 0) {
            h = 0;
            continue;
        }
        int j = sa[r - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
            ++h;
        }
        lcp[r - 1] = h;
        if (h > 0) {
            --h;
        }
    }

    int logn = 1;
    while ((1 << logn) < n) {
        ++logn;
    }
    vector<int> lgv(n + 1);
    for (int i = 2; i <= n; ++i) {
        lgv[i] = lgv[i / 2] + 1;
    }
    vector<vector<int>> st(logn, vector<int>(max(n - 1, 0)));
    if (n > 1) {
        st[0] = lcp;
        for (int p = 1; p < logn; ++p) {
            int span = 1 << p;
            int half = 1 << (p - 1);
            for (int i = 0; i + span <= n - 1; ++i) {
                st[p][i] = min(st[p - 1][i], st[p - 1][i + half]);
            }
        }
    }

    auto suffix_lcp = [&](int i, int j) -> int {
        if (i == j) {
            return n - i;
        }
        int ri = rnk[i];
        int rj = rnk[j];
        if (ri > rj) {
            swap(ri, rj);
        }
        int width = rj - ri;
        int p = lgv[width];
        return min(st[p][ri], st[p][rj - (1 << p)]);
    };

    for (int qi = 0; qi < q; ++qi) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        --l1;
        --r1;
        --l2;
        --r2;
        int len1 = r1 - l1 + 1;
        int len2 = r2 - l2 + 1;
        int common = suffix_lcp(l1, l2);
        int lim = min(len1, len2);
        bool leq;
        if (common >= lim) {
            leq = len1 <= len2;
        } else {
            leq = s[l1 + common] < s[l2 + common];
        }
        cout << (leq ? "YES\n" : "NO\n");
    }
    return 0;
}

Comments

There are no comments at the moment.