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

╰半橙微兮° 2021-09-30 01:28 329阅读 0赞

[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; }

转载于:https://www.cnblogs.com/dummyummy/p/10935225.html

[RemoteJudge]: https://www.luogu.org/problemnew/show/CF700E
[CF666E]: https://www.cnblogs.com/dummyummy/p/10932735.html