On Atcoder Beginner Contest 272F -- Two Strings

Правка en4, от CristianoPenaldo, 2022-10-09 05:48:10

Please note that this blog is a review of this problem. It is not novel enough to be an editorial. This problem may not be difficult for those people who are beyond purple, but very difficult for me.

To be more self-contained, I copy the problem here:

Problem Statement:

You are given strings S and T of length N each, consisting of lowercase English letters.

For a string $$$X$$$ and an integer $$$i$$$, let $$$f(X,i)$$$ be the string obtained by performing on $$$X$$$ the following operation $$$i$$$ times:

Remove the first character of $$$X$$$ and append the same character to the end of X. Find the number of integer pairs $$$(i,j)$$$ satisfying $$$0≤i,j≤N−1$$$ such that $$$f(S,i) \leq f(T,j)$$$ lexicographically.

For example, when $$$n=3$$$, S="adb", T="cab", there are 4 pairs: (1)$$$i=j=0$$$, "adb" <= "cab"; (2)$$$i=2, j=0$$$, "bad" <= "cab"; (3)$$$i=0, j=2$$$, "adb" <= "bca"; (4)$$$i=j=2$$$, "bad" <= "bca". You can find more test cases here: https://atcoder.jp/contests/abc272/tasks/abc272_f

Here the problem statement ends. Now we analyze this problem.

The operation $$$f$$$ is a cyclic shift (CS). String concatenation is a powerful tool to handle string CS, eg, for $$$i=2$$$, f(S, 2)= "bad" is a substring of "adbadb". The string concatenation gets rid of mod operation to find index after CS, since mod operation is quite difficult to handle.

Let $$$S2=S+S$$$, $$$T2=T+T$$$. Here we want to count the pair $$$(i, j)$$$ such that $$$S2.substr(i, n) \leq T2.substr(j, n)$$$. But this still requires $$$O(n^3)$$$ complexity. So here we need another tool: suffix array. Suffix array sorts the suffix of a string. For example, the suffix array of "baad" is $$$\{1, 2, 0, 3\}$$$, because the lexicographic order (from small to big) is: ("aad" $$$1$$$, "ad" $$$2$$$, "baad" $$$0$$$, "d" $$$3$$$). Please note that the SA-IS algorithm could compute suffix array efficiently enough in O(Length of String). Here is the example code, you may find an implementation of SA-IS here:

#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(x) (int)(x).size()
#define fastio cin.tie(0) -> sync_with_stdio(0)
#define pii pair<int, int>
#define ll long long
#define F(i, a, b) for(int i=(a); i <= (b); ++i)
#define SUM 1
#define MAX 0
#define pii pair<int, int>
#define pll pair<ll, ll>
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define HERE cout << "HERE: " << __LINE__ << "\n";

template<typename T, T...>
struct myinteger_sequence { };

template<typename T, typename S1 = void, typename S2 = void>
struct helper{
    std::string operator()(const T& s){
        return std::string(s);
    }
}; 

template<typename T>
struct helper<T, decltype((void)std::to_string(std::declval<T>())), typename std::enable_if<!std::is_same<typename std::decay<T>::type, char>::value, void>::type>{
    std::string operator()(const T& s){
        return std::to_string(s);
    }
};

template<typename T>
struct helper<T, void, typename std::enable_if<std::is_same<typename std::decay<T>::type, char>::value, void>::type>{
    std::string operator()(const T& s){
        return std::string(1, s);
    }
};

template<typename T, typename S1 =void, typename S2 =void>
struct seqhelper{
    const static bool seq = false;
};

template<typename T>
struct seqhelper<T, decltype((void)(std::declval<T>().begin())), decltype((void)(std::declval<T>().end()))>{
    const static bool seq = !(std::is_same<typename std::decay<T>::type, std::string>::value);
};

template<std::size_t N, std::size_t... I>
struct gen_indices : gen_indices<(N - 1), (N - 1), I...> { };
template<std::size_t... I>
struct gen_indices<0, I...> : myinteger_sequence<std::size_t, I...> { };

template<typename T, typename REDUNDANT = void>
struct converter{
    template<typename H>
    std::string& to_string_impl(std::string& s, H&& h)
    {
        using std::to_string;
        s += converter<H>().convert(std::forward<H>(h));
        return s;    
    }

    template<typename H, typename... T1>
    std::string& to_string_impl(std::string& s, H&& h, T1&&... t)
    {
        using std::to_string;
        s += converter<H>().convert(std::forward<H>(h)) + ", ";
        return to_string_impl(s, std::forward<T1>(t)...);
    }

    template<typename... T1, std::size_t... I>
    std::string mystring(const std::tuple<T1...>& tup, myinteger_sequence<std::size_t, I...>)
    {
        std::string result;
        to_string_impl(result, std::get<I>(tup)...);
        return result;
    }

    template<typename... S>
    std::string mystring(const std::tuple<S...>& tup)
    {
        return mystring(tup, gen_indices<sizeof...(S)>{});
    }

    template<typename S=T>
    std::string convert(const S& x){
        return helper<S>()(x);
    }

    template<typename... S>
    std::string convert(const std::tuple<S...>& tup){
        std::string res = std::move(mystring(tup));
        res = "{" + res + "}";
        return res;
    }

    template<typename S1, typename S2>
    std::string convert(const std::pair<S1, S2>& x){
        return "{" + converter<S1>().convert(x.first) + ", " + converter<S2>().convert(x.second) + "}";
    }
};

template<typename T>
struct converter<T, typename std::enable_if<seqhelper<T>::seq, void>::type>{
    template<typename S=T>
    std::string convert(const S& x){
        int len = 0;
        std::string ans = "{";
        for(auto it = x.begin(); it != x.end(); ++it){
            ans += move(converter<typename S::value_type>().convert(*it)) + ", ";
            ++len;
        }
        if(len == 0) return "{[EMPTY]}";
        ans.pop_back(), ans.pop_back();
        return ans + "}";
    }
};

template<typename T>
std::string luangao(const T& x){
    return converter<T>().convert(x);
}

namespace atcoder {

namespace internal {

std::vector<int> sa_naive(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n);
    std::iota(sa.begin(), sa.end(), 0);
    std::sort(sa.begin(), sa.end(), [&](int l, int r) {
        if (l == r) return false;
        while (l < n && r < n) {
            if (s[l] != s[r]) return s[l] < s[r];
            l++;
            r++;
        }
        return l == n;
    });
    return sa;
}

std::vector<int> sa_doubling(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n), rnk = s, tmp(n);
    std::iota(sa.begin(), sa.end(), 0);
    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int x, int y) {
            if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
            int rx = x + k < n ? rnk[x + k] : -1;
            int ry = y + k < n ? rnk[y + k] : -1;
            return rx < ry;
        };
        std::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);
        }
        std::swap(tmp, rnk);
    }
    return sa;
}

// SA-IS, linear-time suffix array construction
// Reference:
// G. Nong, S. Zhang, and W. H. Chan,
// Two Efficient Algorithms for Linear Time Suffix Array Construction
template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
    int n = int(s.size());
    if (n == 0) return {};
    if (n == 1) return {0};
    if (n == 2) {
        if (s[0] < s[1]) {
            return {0, 1};
        } else {
            return {1, 0};
        }
    }
    if (n < THRESHOLD_NAIVE) {
        return sa_naive(s);
    }
    if (n < THRESHOLD_DOUBLING) {
        return sa_doubling(s);
    }

    std::vector<int> sa(n);
    std::vector<bool> ls(n);
    for (int i = n - 2; i >= 0; i--) {
        ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
    }
    std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
    for (int i = 0; i < n; i++) {
        if (!ls[i]) {
            sum_s[s[i]]++;
        } else {
            sum_l[s[i] + 1]++;
        }
    }
    for (int i = 0; i <= upper; i++) {
        sum_s[i] += sum_l[i];
        if (i < upper) sum_l[i + 1] += sum_s[i];
    }

    auto induce = [&](const std::vector<int>& lms) {
        std::fill(sa.begin(), sa.end(), -1);
        std::vector<int> buf(upper + 1);
        std::copy(sum_s.begin(), sum_s.end(), buf.begin());
        for (auto d : lms) {
            if (d == n) continue;
            sa[buf[s[d]]++] = d;
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        sa[buf[s[n - 1]]++] = n - 1;
        for (int i = 0; i < n; i++) {
            int v = sa[i];
            if (v >= 1 && !ls[v - 1]) {
                sa[buf[s[v - 1]]++] = v - 1;
            }
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        for (int i = n - 1; i >= 0; i--) {
            int v = sa[i];
            if (v >= 1 && ls[v - 1]) {
                sa[--buf[s[v - 1] + 1]] = v - 1;
            }
        }
    };

    std::vector<int> lms_map(n + 1, -1);
    int m = 0;
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms_map[i] = m++;
        }
    }
    std::vector<int> lms;
    lms.reserve(m);
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms.push_back(i);
        }
    }

    induce(lms);

    if (m) {
        std::vector<int> sorted_lms;
        sorted_lms.reserve(m);
        for (int v : sa) {
            if (lms_map[v] != -1) sorted_lms.push_back(v);
        }
        std::vector<int> rec_s(m);
        int rec_upper = 0;
        rec_s[lms_map[sorted_lms[0]]] = 0;
        for (int i = 1; i < m; i++) {
            int l = sorted_lms[i - 1], r = sorted_lms[i];
            int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
            int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
            bool same = true;
            if (end_l - l != end_r - r) {
                same = false;
            } else {
                while (l < end_l) {
                    if (s[l] != s[r]) {
                        break;
                    }
                    l++;
                    r++;
                }
                if (l == n || s[l] != s[r]) same = false;
            }
            if (!same) rec_upper++;
            rec_s[lms_map[sorted_lms[i]]] = rec_upper;
        }

        auto rec_sa =
            sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);

        for (int i = 0; i < m; i++) {
            sorted_lms[i] = lms[rec_sa[i]];
        }
        induce(sorted_lms);
    }
    return sa;
}

}  // namespace internal

std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
    assert(0 <= upper);
    for (int d : s) {
        assert(0 <= d && d <= upper);
    }
    auto sa = internal::sa_is(s, upper);
    return sa;
}

template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
    int n = int(s.size());
    std::vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
    std::vector<int> s2(n);
    int now = 0;
    for (int i = 0; i < n; i++) {
        if (i && s[idx[i - 1]] != s[idx[i]]) now++;
        s2[idx[i]] = now;
    }
    return internal::sa_is(s2, now);
}

std::vector<int> suffix_array(const std::string& s) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return internal::sa_is(s2, 255);
}

}  // namespace atcoder


void debug(){
    #if DEBUG
    freopen("test1.txt", "r", stdin); 
    #else
    fastio;
    #endif      
}

#define DEBUG 0
#define SINGLE 0

int main(){
    debug();
    vector<int> v = move(atcoder::suffix_array("baad"));
    cout << luangao(v) << "\n"; //{1, 2, 0, 3}
}

Let $$$Sf(S, i)$$$ be the suffix of S from index $$$i$$$ ($$$0$$$-indexed). For example, Sf("abcd", 1) = "bcd". The key idea is making a transform $$$g$$$ of $$$S, T$$$, together with their indices, such that $$$S2.substr(i, n) \leq T2.substr(j, n) \leftrightarrow Sf(g(S2, T2), g(i)) \leq Sf(g(S2, T2), g(j))$$$, where $$$g(S2, T2)$$$ is a large string obtained from $$$S2, T2$$$, and $$$g(i), g(j)$$$ are the transformed indices (because $$$i, j$$$ correspond to other indices different from $$$i, j$$$ in the large string $$$g(S2, T2)$$$). We need to transform the comparison of substrings to the comparison of suffices, by doing so we can utilize the powerful tool: SA-IS.

One failed construction is $$$g(S2, T2) := T2 + S2$$$. For example, $T$="zabf", $T2$="zabfzabf", $S$="abfz", $S2$="abfzabfz", $T2+S2$="z**abf**zabf**abf**zabfz". One can check that, the suffix corresponding to the first "abf" is "abfzabfabfzabfz" and the suffix corresponding to the second "abf" is

Теги string, suffix array

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en28 Английский CristianoPenaldo 2022-10-10 13:36:22 2 Tiny change: 'or $i=2$, f(S, 2)= "bad" is' -> 'or $i=2$, $f(S, 2)$= "bad" is'
en27 Английский CristianoPenaldo 2022-10-09 08:42:55 7 Tiny change: 'y(large));\n ll a' -> 'y(large)); //O(n)\n ll a'
en26 Английский CristianoPenaldo 2022-10-09 08:30:27 4 Tiny change: 'he end of X.\nFind the' -> 'he end of $X$.\n\nFind the' (published)
en25 Английский CristianoPenaldo 2022-10-09 08:29:48 14 (saved to drafts)
en24 Английский CristianoPenaldo 2022-10-09 07:27:30 43
en23 Английский CristianoPenaldo 2022-10-09 07:19:38 1 Tiny change: 's/abc272_f\n\nHere t' -> 's/abc272_f.\n\nHere t'
en22 Английский CristianoPenaldo 2022-10-09 07:18:12 105
en21 Английский CristianoPenaldo 2022-10-09 07:05:55 0 (published)
en20 Английский CristianoPenaldo 2022-10-09 07:03:47 43 (saved to drafts)
en19 Английский CristianoPenaldo 2022-10-09 07:02:30 8
en18 Английский CristianoPenaldo 2022-10-09 07:01:21 2 Tiny change: '498339).\nCorrect ' -> '498339).\n\nCorrect ' (published)
en17 Английский CristianoPenaldo 2022-10-09 07:00:34 94
en16 Английский CristianoPenaldo 2022-10-09 06:56:20 772 Tiny change: 'ntrol.\n\nWe nee' -> 'ntrol.\n\n\n\nWe nee'
en15 Английский CristianoPenaldo 2022-10-09 06:40:46 18
en14 Английский CristianoPenaldo 2022-10-09 06:39:39 147
en13 Английский CristianoPenaldo 2022-10-09 06:36:51 6
en12 Английский CristianoPenaldo 2022-10-09 06:36:06 499
en11 Английский CristianoPenaldo 2022-10-09 06:33:02 336
en10 Английский CristianoPenaldo 2022-10-09 06:27:22 147
en9 Английский CristianoPenaldo 2022-10-09 06:22:37 125
en8 Английский CristianoPenaldo 2022-10-09 06:09:02 410
en7 Английский CristianoPenaldo 2022-10-09 06:03:25 532
en6 Английский CristianoPenaldo 2022-10-09 05:53:58 405
en5 Английский CristianoPenaldo 2022-10-09 05:49:03 10
en4 Английский CristianoPenaldo 2022-10-09 05:48:10 162 Tiny change: '$="z$\textbf{abf}$zabf' -> '$="z$\texttt{abf}$zabf'
en3 Английский CristianoPenaldo 2022-10-09 05:43:27 315
en2 Английский CristianoPenaldo 2022-10-09 05:28:20 515
en1 Английский CristianoPenaldo 2022-10-09 05:22:02 12387 Initial revision (saved to drafts)