题意：给一个模板串 $S$，$q$次询问，每次求模板串 $S[L,R]$内恰好在字典序上严格大于 $T$串的一个串 $S_1$
用来复健 $SAM$的一道题。
挺模板的，首先做过 NOI2018 你的名字的同学一定会想到用线段树合并维护 $SAM$上每个节点的 $Right$集合，我们每次可以用 $logn$的时间 $query$下一个状态是否在合法的区间内。
这道题就是在此基础上每一步贪心选择在 $SAM$上可以走的状态，假设我们已经知道所有 $SAM$上的节点在当前的询问下是否可以走，那么我们尽量沿着 $T$串走，即让 $T[1..(i-1)]$在 $SAM$上跑，假设我们走到 $T[i]$发现它已经不在自动机上了，那么我们可以直接检索 $(T[i] +１)～‘z’$看其是否在自动机上 (即顺序查找字典序意义上严格大于 $T[i]$的字符)，如果在，设此时枚举到字符 $c$，那么答案就是 $T[1..(i-1)]+c$，如果查完也没有找到，就回到自动机上的上一个状态进行枚举，直到找到。
注意到还有一种情况就是整个字符串 $T$跑完之后当前状态仍然在自动机上，我们可以人为把 $T$加长一位 $T[len_T + 1] = 0$（假设 $’a’~’z’$分别对应 $1~26$），这样就免去了特判。
因为线段树合并打错调了两个钟的 $qhy$事屑。
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define N 1000005
#define mod 1000000007
#define ll long long
#define F first
#define S second
#define mp(i, j) std::make_pair(i, j)
#define ls t[u][0]
#define rs t[u][1]
ll ans;
int n, k, m, len, t[N * 20][2], idx, rt[N], up;
char s[N];
void insert (int &u, int l, int r, int p)
{
if (!u)
u = ++idx;
if (l == r) return;
int mid = l + r >> 1;
if (p <= mid) insert(ls, l, mid, p);
else insert(rs, mid + 1, r, p);
}
int merge (int l, int r)
{
if (!l || !r) return l | r;
int u = ++idx;
ls = merge(t[l][0], t[r][0]);
rs = merge(t[l][1], t[r][1]);
return u;
}
bool query (int u, int l, int r, int x, int y)
{
if (!u || x > y) return 0;
if (x <= l && r <= y) return 1;
int mid = l + r >> 1;
bool ret = 0;
if (x <= mid) ret |= query(ls, l, mid, x, y);
if (ret) return ret;
if (mid < y) ret |= query(rs, mid + 1, r, x, y);
return ret;
}
struct SAM { // N = n * 2
int ch[N][27], step[N], pre[N], cnt, last, a[N], b[N], u, l;
inline void init ()
{
memset(ch, 0, sizeof ch);
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
memset(step, 0, sizeof step);
memset(pre, 0, sizeof pre);
cnt = last = 1;
u = 1, l = 0;
}
inline int ins (int x)
{
int p = last;
if (ch[p][x])
{
int q = ch[p][x];
if (step[p] + 1 == step[q]) {return q;}
int nq = ++cnt;
step[nq] = step[p] + 1;
memcpy(ch[nq], ch[q], sizeof ch[q]);
pre[nq] = pre[q]; pre[q] = nq;
while (ch[p][x] == q) ch[p][x] = nq, p = pre[p];
return nq;
}
int np = ++cnt;
last = cnt; step[np] = step[p] + 1;
while (p && !ch[p][x]) ch[p][x] = np, p = pre[p];
if (!p)
pre[np] = 1;
else
{
int q = ch[p][x];
if (step[q] == step[p] + 1)
pre[np] = q;
else
{
int nq = ++cnt;
step[nq] = step[p] + 1;
memcpy(ch[nq], ch[q], sizeof ch[q]);
pre[nq] = pre[q]; pre[q] = pre[np] = nq;
while (ch[p][x] == q) ch[p][x] = nq, p = pre[p];
}
}
return np;
}
inline void init2 ()
{
fo (i, 1, cnt) a[step[i]]++;
fo (i, 1, cnt) a[i] += a[i - 1];
fo (i, 1, cnt) b[a[step[i]]--] = i;
fd (j, cnt, 1)
{
int i = b[j];
rt[pre[i]] = merge(rt[pre[i]], rt[i]);
}
return;
}
inline void print ()
{
fo (i, 1, cnt)
fo (j, 0, 25)
if (ch[i][j])
printf("%d --%c--> %d \n", i, j + 'a' - 1, ch[i][j]);
fo (i, 1, cnt)
printf("pre[%d] = %d \n", i, pre[i]);
}
int q[N], tt;
int x, y;
char w[N];
inline void solve (int l, int r)
{
int u = 1, pos;
++n;
fo (i, 1, n)
if (ch[u][s[i]] && query(rt[ch[u][s[i]]], 1, up, l + i - 1, r))
{
q[i] = u;
u = ch[u][s[i]];
}
else
{
q[i] = u;
pos = i;
break;
}
fo (j, 1, pos - 1) w[j] = s[j] + 'a' - 1;
while (pos)
{
int u = q[pos];
fo (j, s[pos] + 1, 26)
if (ch[u][j] && query(rt[ch[u][j]], 1, up, l + pos - 1, r))
{
w[pos] = j + 'a' - 1;
fo (k, 1, pos) printf("%c", w[k]);
puts("");
return;
}
--pos;
}
printf("-1\n");
return;
}
} sam;
int main ()
{
scanf("%s", s + 1);
up = n = strlen(s + 1);
sam.init();
fo (i, 1, n) sam.last = sam.ins(s[i] - 'a' + 1), insert(rt[sam.last], 1, n, i);
sam.init2();
int l, r;
scanf("%d", &m);
while (m--)
{
scanf("%d %d", &l, &r);
scanf("%s", s + 1);
n = strlen(s + 1);
s[n + 1] = 0;
fo (i, 1, n) s[i] -= 'a' - 1;
sam.solve(l, r);
}
return 0;
}
0 条评论