CF700E Cool Slogans——SAM+线段树合并

RemoteJudge

又是一道用线段树合并来维护\(endpos\)的题，还有一道见我的博客CF666E

思路

先把\(SAM\)建出来

如果两个相邻的串\(s_i\)和\(s_{i+1}\)要满足\(s_i\)在\(s_{i+1}\)中至少出现了两次，那么\(s_i\)显然是\(s_{i+1}\)对应的结点在\(parent\ tree\)上的祖先，那么我们可以在\(parent\ tree\)上树形dp来得出答案

转移自顶向下进行，\(s_i\)在\(s_{i+1}\)中至少出现了两次意味着\(s_i\)在\(s_{i+1}\)的所有\(endpos\)位置都出现了两次，所以我们只需要知道\(s_{i+1}\)的\(endpos\)中任意一个元素并结合线段树来判断能否从\(s_i\)向\(s_{i+1}\)转移。我直接维护了一个\(firstpos\)代表\(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

int n;

char s[N+5];

struct SAM {

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

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

  vi G[2*N+5];

  int top[2*N+5];

  ll f[2*N+5], ans;

  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(!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 pos) {

    int cur = ++tot;

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

    firstpos[cur] = pos;

    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;

        firstpos[clone] = firstpos[q];

        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', i);

    }

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

    dfs(1);

  }

  void dp(int u) { // top数组用来辅助转移

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

      v = G[u][i];

      if(u == 1) f[v] = 1, top[v] = v;

      else {

        if(query(root[top[u]], 1, n, firstpos[v]-maxlen[v]+maxlen[top[u]], firstpos[v]) >= 2) f[v] = f[u]+1, top[v] = v;

        else f[v] = f[u], top[v] = top[u];

      }

      ans = max(ans, f[v]);

      dp(v);

    }

  }

  ll getans() {

    dp(1);

    return ans;

  }

}sa;

int main() {

  scanf("%d", &n);

  scanf("%s", s+1);

  sa.build();

  printf("%lld\n", sa.getans());

  return 0;

}

巴特西

CF700E Cool Slogans——SAM+线段树合并

思路

最新文章

热门文章