2021年ICPC国际大学生程序设计竞赛暨陕西省第九届大学生程序设计竞赛 L:String Games

题目链接：String Games

题意：

给定串$S$，$q$个询问，每次询问一个子串$[l,r]$，找出一个子串的字典序比它大且在所有符合的字串中的字典序是最小的。输出其长度和结尾字符。

思路：

我们有一个很明显的贪心思路：
我们设$len=r-l+1,T=s[l,r]$，那么我们找一个子串长度为$len+1$，前$len$个字符是子串$T$，第$len+1$个字符尽可能的小。那么我们转化一下也就是找一个后缀$i$，满足$lcp(s[i,n],s[l,n])\ge len$且字典序最小。那么我们可以求一下后缀数组，可以很快速的求出其$lcp$。$lcp(sa[i],sa[j])=min(height[i+1],height[i+2],...,height[j])$。我们可以预处理$RMQ+二分$处理答案。
那么我们如果找不到怎么办？那么就直接去找下一个字典序大的后缀。

code:

const int N = 1e5 + 10, M = N * 2, mod = 1e9 + 7;

char s[N];
int n, sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N];
int height[N], f[N][22];

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr); cin.tie(nullptr);

    int i, m = 300, p, w, k;
    scanf("%s", s + 1);
    n = strlen(s + 1);

    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1;; w <<= 1, m = p) {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
        if (sa[i] > w) id[++p] = sa[i] - w;
        memset(cnt, 0, sizeof(cnt));
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
        memcpy(oldrk, rk, sizeof(rk));
        for (p = 0, i = 1; i <= n; ++i)
        rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
        if (p == n) {
            for (int i = 1; i <= n; ++i) sa[rk[i]] = i;
            break;
        }
    }

    for (i = 1, k = 0; i <= n; ++i) {
        if (rk[i] == 0) continue;
        if (k) --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        height[rk[i]] = k;
    }
    for(int i = 1; i <= n; i++) f[i][0] = height[i];
    for(int j = 1; j <= 20; j++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
    auto check = [&](int x, int y) -> int {
        // if(x > y) swap(x, y);
        x++;
        int len = y - x + 1;
        len = __lg(len);
        return min(f[x][len], f[y - (1 << len) + 1][len]);
    };
    int Q; cin >> Q;
    while(Q--) {
        int L, R;
        cin >> L >> R;
        int l = 1, r = rk[L];
        int t = rk[L];
        int len = R - L + 1;
        while(l <= r) {
            int mid = l + r >> 1;
            if(check(mid, rk[L]) >= len) {
                t = mid, r = mid - 1;
            }
            else l = mid + 1;
        } 
        if(n - sa[t] + 1 > len) {
            cout << len + 1 << ' ' << s[sa[t] + len] << '\n';
            continue;
        }
        t++;
        if(t > n) {
            cout << "0\n";
            continue;
        }
        int res = check(t - 1, t);
        cout << res + 1 << ' ' << s[sa[t] + res] << '\n';
    }


    return 0;
}
/*
*/