传送门

题意:给一个模板串 $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] +1)~‘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;
}
分类: 文章

quhengyi11

明日は何になる? やがて君になる!

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code