CodeForces 1537E - Erase and Extend 题解

当时有个细节没想到，直接 fst

首先不难证明最终的字符串一定是由 $s$ 的一个前缀不断重复得到的。所以我们可以枚举前缀的位置 $i$ ，如果从 $i$ 开始重复能使得新字符串比原字符串小的话这个位置就是有利的，同时根据字典序的规则， $i$ 肯定是越靠前越好，于是我们就得到了策略：将 $s_{i\dots n}$ 与 $s$ 比较，从比 $s$ 大的中找出 $i$ 最小的那个。我比赛的时候一看这不就是后缀数组嘛，过了 pretest 心里美滋滋，结果 system test 的时候：

FST 图片

那么问题出在哪了呢？我们来看这个例子 $s=bab$ 。当 $i=2$ 时， $s_{2\dots 2}=b$ 是 $s$ 的一个前缀，看似 $b$ 比较小，但由于字符串是循环的所以补上一个 $s$ 之后变为 $bbab$ 就比 $s$ 大了。所以这种情况也就是说 $s$ 的某个后缀等于前缀，我们接下来说明扔掉这个后缀可以获得更好的答案：假设这个后缀的长度是 $i$ ， $s$ 与 $s_{0\dots n-i-1}$ 循环一次后会在 $s$ 与 $s_{i\dots n-1}$ 对应的位置发生不同，比如说 $s=cbcacb$ 循环之后是这样的

\begin{align*}&cbcacb|\underline{cbcacb} \\\ &cbca|cb\underline{ca} \end{align*}

其中竖线用来分隔循环，下划线是两个字符串开始不同的位置。可以证明 $s\ge s_{i\dots n-1}$ ,因为如果小于的话，由于 $i<n-i-1$ ，所以 $i$ 就是更好的位置，也就用不到考虑后缀的情况了，因此我们说明了扔掉后缀一定是更好的选择，所以我们要想办法让后缀在后缀数组中排在 $s$ 后面，于是我们可以在 $s$ 后面加一个大于所有字母的字符，这样就保证了如果有后缀是 $s$ 的前缀的情况，后缀一定排在 $s$ 后面。这样我们就得到了用比较无脑的用后缀数组的做法：

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> suffix_array(string s) {
    s += "#";
    int n = s.size(), N = n + 256;
    vector<int> sa(n), ra(n);
    for (int i = 0; i < n; i++)
        sa[i] = i, ra[i] = s[i];
    for (int k = 0; k < n; k ? k *= 2 : k++) {
        vector<int> nsa(sa), nra(n), cnt(N);
        for (int i = 0; i < n; i++) nsa[i] = (nsa[i] - k + n) % n;
        for (int i = 0; i < n; i++) cnt[ra[i]]++;
        for (int i = 1; i < N; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[ra[nsa[i]]]] = nsa[i];
 
        int r = 0;
        for (int i = 1; i < n; i++) {
            if (ra[sa[i]] != ra[sa[i - 1]]) r++;
            else if (ra[(sa[i] + k) % n] != ra[(sa[i - 1] + k) % n])
                r++;
            nra[sa[i]] = r;
        }
        ra = nra;
    }
    sa.erase(sa.begin());
    return sa;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string s;
    cin >> n >> k >> s;
    s += '|';
    auto sa = suffix_array(s);
    int ii = find(sa.begin(), sa.end(), 0) - sa.begin();
    int mn = *min_element(sa.begin() + ii + 1, sa.end());
    for (int i = 0; i < k; i++)
        cout << s[i % mn];
    return 0;
}

但是后缀数组有点杀鸡用牛刀了，我们其实只用和 $s$ 做比较，所以另一种更简单的做法是用z 函数，因为 z 函数求的是与整个字符串的最长公共前缀，所以比较前缀后下一个字符就能知道大小关系了。对于后缀的特殊情况，如果下一个字符的位置是 $n$ 也就说明 $s_{i\dots n-1}$ 是 $s$ 的前缀，所以此时 $i$ 的位置就是最佳位置。代码如下：

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> z_function(const string &s) {
    int n = (int)s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string s;
    cin >> n >> k >> s;
    auto z = z_function(s);
    for (int i = 1; i < n; i++) {
        int f = z[i];
        if (f + i >= n || s[f] < s[f + i]) {
            s.erase(s.begin() + i, s.end());
            break;
        }
    }
    for (int i = 0; i < k; i++)
        cout << s[i % s.size()];
    return 0;
}