Description
给出一个字符串 (S)。
给出 (Q) 个操作，给出 (L, R, T)，求字典序最小的 (S_1)，使得 (S^prime) 为(S[L..R]) 的子串，且 (S^prime) 的字典序严格大于 (T)。输出这个 (S^prime) ，如果无解输出 -1。
Hint
- (1le |S|le 10^5)
- (1le Qle 2 imes 10^5)
- (1le Lle Rle |S|)
- (1le sum |T| le 2 imes 10^5)
Solution
看到各种“子串”，考虑 SAM。
要求“字典序严格大于 (T) 的字典序最小子串”，那么有一个 贪心 的方法：找一个 (T) 的 前缀，后面加一个字典序稍大的字符。
这样的话直接把 (T) 放到 (S) 的 SAM 上跑，求出 每一位如果替换掉的话可以换的最小字符 ( ext{dir})。没有的话就是 (-1)。
然后整出 ( ext{dir}) 之后，倒着 看看有没有 ( ext{dir}
e -1) 的位置，有就换掉这一位然后输出，否则答案就是 -1。
注意答案长度可能会比 (T) 大一，所以 ( ext{dir}) 要算到 (|T| + 1) 位。
还有一个问题，就是怎么处理区间限制？
这就需要 ( ext{end-pos}) 了。我指 处理出整个集合。 可以用树上主席树或线段树合并维护。这样可以快速判断 ( ext{end-pos}) 中 是否含有某个区间中的值。 这样在用 (T) 在 SAM 上跑的时候就可以只走区间中的点，替换字符也可以只换可以到达区间中的点。
时空复杂度 (O(nlog n))，这里将 (Sigma = 26) 记为常数。
Code
实现比较复杂，注意细节。
线段树合并。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : Codeforces 1037H Security
*/
#include <iostream>
#include <map>
#include <string>
using namespace std;
const int Len = 1e5 + 5;
namespace segt {
const int S = Len << 6;
int lc[S], rc[S];
int total = 0;
#define mid ((l + r) >> 1)
void insert(int& x, int p, int l = 1, int r = Len) {
if (!x) x = ++total;
if (l == r) return;
if (p <= mid) insert(lc[x], p, l, mid);
else insert(rc[x], p, mid + 1, r);
}
int merge(int x, int y, int l = 1, int r = Len) {
if (l == r || !x || !y) return x | y;
int z = ++total;
lc[z] = merge(lc[x], lc[y], l, mid);
rc[z] = merge(rc[x], rc[y], mid + 1, r);
return z;
}
bool find(int u, int v, int x, int l = 1, int r = Len) {
if (!x) return false;
if (u <= l && r <= v) return true;
if (u <= mid && find(u, v, lc[x], l, mid)) return true;
if (v > mid && find(u, v, rc[x], mid + 1, r)) return true;
return false;
}
};
namespace SAM {
const int T = Len << 1;
struct Node {
map<char, int> ch;
int link, len, eprt;
} t[T];
int total;
int last;
void extend_char(char c) {
int p = last, np = last = ++total;
t[np].len = t[p].len + 1;
for (; p && !t[p].ch[c]; p = t[p].link)
t[p].ch[c] = np;
if (!p) {
t[np].link = 1;
} else {
int q = t[p].ch[c];
if (t[p].len + 1 == t[q].len) {
t[np].link = q;
} else {
int nq = ++total;
t[nq] = t[q], t[nq].len = t[p].len + 1;
t[np].link = t[q].link = nq;
for (; p && t[p].ch[c] == q; p = t[p].link)
t[p].ch[c] = nq;
}
}
segt::insert(t[np].eprt, t[np].len);
}
int b[T], c[T];
void topo_sort() {
for (register int i = 1; i <= total; i++) ++c[t[i].len];
for (register int i = 1; i <= total; i++) c[i] += c[i - 1];
for (register int i = 1; i <= total; i++) b[c[t[i].len]--] = i;
}
void init_end_pos() {
for (register int i = total; i; i--) {
int x = b[i], f = t[x].link;
if (f) t[f].eprt = segt::merge(t[x].eprt, t[f].eprt);
}
}
void init_data(string& s) {
total = last = 1;
for (string::iterator it = s.begin(); it != s.end(); it++)
extend_char(*it);
topo_sort();
init_end_pos();
}
int dir[Len];
string query(int l, int r, string str);
};
string SAM::query(int l, int r, string str) {
int x = 1, y, i;
for (i = 1; ; i++) {
dir[i] = -1;
char c = (i > str.size()) ? 'a' : str[i - 1] + 1;
map<char, int>::iterator it = t[x].ch.lower_bound(c);
for (; it != t[x].ch.end(); it++) {
y = it->second;
if (segt::find(l + i - 1, r, t[y].eprt)) {
dir[i] = it->first;
break;
}
}
c = (i > str.size()) ? 0 : str[i - 1];
y = t[x].ch[c];
if (!y || i == str.size() + 1 || !segt::find(l + i - 1, r, t[y].eprt))
break;
x = y;
}
for (; i && dir[i] == -1; i--);
if (!i) return "-1";
string ret;
for (register int j = 1; j < i; j++)
ret += str[j - 1];
ret += dir[i];
return ret;
}
signed main() {
ios::sync_with_stdio(false);
string str;
cin >> str;
SAM::init_data(str);
int q;
cin >> q;
while (q--) {
int L, R;
cin >> L >> R >> str;
cout << SAM::query(L, R, str) << '
';
}
return 0;
}