CF1037H Security——SAM+线段树合并

又是一道\(SAM\)维护\(endpos\)集合的题，我直接把CF700E的板子粘过来了QwQ

思路

如果我们有\([l,r]\)对应的\(SAM\)，只需要在上面贪心就可以了。因为要求的是字典序比\(T\)大且最小的子串，我们从前到后让尽可能多的位相等，如果再也无法相等了就从后往前找一位变大。

但是每次询问会给我们一个可行区间\([l,r]\)，而我们又显然不能直接把对应区间的\(SAM\)建出来，否则复杂度会\(GG\)。

仔细想一下，其实我们并不需要知道\([l,r]\)区间对应的\(SAM\)，只要知道能否向某一个结点转移就行了。这个我们可以用\(endpos\)集合来判断。具体一下，就是当前已经考虑了\(i\)个字符且在结点\(u\)，现在需要判断能否转移到\(v\)，只需要判断\(u\)是否有到\(v\)的转移边和\(v\)结点的\(endpos\)是否有元素在\([l+i-1,r]\)中就行了

\(endpos\)拿线段树合并维护一下就行了（也可以用树上主席树搞一下）

其实本菜鸡来学这个套路完全是为写你的名字做铺垫的

#include <algorithm>

#include  <iostream>

#include   <cstdlib>

#include   <cstring>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <cmath>

#include     <ctime>

#include     <queue>

#include       <map>

#include       <set>

using namespace std;

#define IINF 0x3f3f3f3f3f3f3f3fLL

#define ull unsigned long long

#define pii pair<int, int>

#define uint unsigned int

#define mii map<int, int>

#define lbd lower_bound

#define ubd upper_bound

#define INF 0x3f3f3f3f

#define vi vector<int>

#define ll long long

#define mp make_pair

#define pb push_back

#define N 200000

#define Q 200000

int n, q, m;

char s[N+5], t[N+5], ans[N+5];

struct SAM {

  int nxt[26][2*N+5], maxlen[2*N+5], link[2*N+5], tot, lst;

  int sumv[100*N+5], ch[2][100*N+5], root[2*N+5], nid;

  int node[N+5];

  vi G[2*N+5];

  void init() {

    tot = lst = 1;

    nid = 0;

  }

  void pushup(int o) {

    sumv[o] = sumv[ch[0][o]]+sumv[ch[1][o]];

  }

  void add(int &o, int l, int r, int x) {

    if(!o) o = ++nid;

    if(l == r) {

      sumv[o] = 1;

      return ;

    }

    int mid = (l+r)>>1;

    if(x <= mid) add(ch[0][o], l, mid, x);

    else add(ch[1][o], mid+1, r, x);

    pushup(o);

  }

  int merge(int o, int u, int l, int r) {

    if(!o || !u) return o|u;

    int v = ++nid;

    if(l == r) {

      sumv[v] = sumv[o]+sumv[u] ? 1 : 0;

      return v;

    }

    int mid = (l+r)>>1;

    ch[0][v] = merge(ch[0][o], ch[0][u], l, mid);

    ch[1][v] = merge(ch[1][o], ch[1][u], mid+1, r);

    pushup(v);

    return v;

  }

  int query(int o, int l, int r, int L, int R) {

    if(L > R || !o) return 0;

    if(L <= l && r <= R) return sumv[o];

    int ret = 0, mid = (l+r)>>1;

    if(L <= mid) ret += query(ch[0][o], l, mid, L, R);

    if(R > mid) ret += query(ch[1][o], mid+1, r, L, R);

    return ret;

  }

  void extend(int c) {

    int cur = ++tot;

    maxlen[cur] = maxlen[lst]+1;

    while(lst && !nxt[c][lst]) nxt[c][lst] = cur, lst = link[lst];

    if(!lst) link[cur] = 1;

    else {

      int p = lst, q = nxt[c][p];

      if(maxlen[q] == maxlen[p]+1) link[cur] = q;

      else {

        int clone = ++tot;

        maxlen[clone] = maxlen[p]+1;

        link[clone] = link[q], link[q] = link[cur] = clone;

        for(int i = 0; i < 26; ++i) nxt[i][clone] = nxt[i][q];

        while(p && nxt[c][p] == q) nxt[c][p] = clone, p = link[p];

      }

    }

    lst = cur;

  }

  void dfs(int u) {

    for(int i = 0, v; i < G[u].size(); ++i) {

      v = G[u][i];

      dfs(v);

      root[u] = merge(root[u], root[v], 1, n);

    }

  }

  void build() {

    init();

    for(int i = 1; i <= n; ++i) {

      add(root[tot+1], 1, n, i);

      extend(s[i]-'a');

    }

    for(int i = 2; i <= tot; ++i) G[link[i]].pb(i);

    dfs(1);

  }

  void search(int L, int R) {

    m = strlen(t+1);

    int u = 1, v, x;

    for(int i = 1; 1; ++i) {

      ans[i] = -1;

      for(int j = max(t[i]-'a'+1, 0); j < 26; ++j) {

        v = nxt[j][u];

        if(v && query(root[v], 1, n, L+i-1, R)) {

          ans[i] = j;

          break;

        }

      }

      v = nxt[max(t[i]-'a', 0)][u];

      x = i;

      if(i == m+1 || !v || !query(root[v], 1, n, L+i-1, R)) break;

      u = v;

    }

    while(x && ans[x] == -1) --x;

    if(!x) printf("-1\n");

    else {

      for(int j = 1; j < x; ++j) printf("%c", t[j]);

      printf("%c\n", ans[x]+'a');

    }

  }

}sam;

int main() {

  scanf("%s%d", s+1, &q);

  n = strlen(s+1);

  sam.build();

  for(int i = 1, L, R; i <= q; ++i) {

    scanf("%d%d%s", &L, &R, t+1);

    sam.search(L, R);

  }

  return 0;

}

巴特西

CF1037H Security——SAM+线段树合并

思路

最新文章

热门文章