BZOJ1396 识别子串 [SAM+线段树]

BZOJ1396 识别子串 [SAM+线段树]

​​传送门​​

显然只有后缀自动机上 right 集合为 1 的才能作为答案

我们先建出 SAM, 考虑一个 right 集合为1 的点的贡献

它在原串的对应点为 pos, 它的长为 Minlen -- Maxlen

于是用线段树维护最小就可以了

#include#define N 400050using namespace std;struct Node{ int ch[26], link, len, pos, siz;} t[N]; int n, tot, last, c[N], A[N]; char s[N];void Extend(int id, int c){ int cur = ++tot, p = last; t[cur].len = t[p].len + 1; t[cur].pos = id; t[cur].siz = 1; for(;p && !t[p].ch[c]; p = t[p].link) t[p].ch[c] = cur; if(!p) t[cur].link = 1; else{ int q = t[p].ch[c]; if(t[q].len == t[p].len + 1) t[cur].link = q; else{ int clone = ++tot; t[clone].link = t[q].link; t[clone].len = t[p].len + 1; for(int i=0; i<26; i++) t[clone].ch[i] = t[q].ch[i]; for(;p && t[p].ch[c] == q; p = t[p].link) t[p].ch[c] = clone; t[q].link = t[cur].link = clone; } } last = cur;}const int inf = 0x3fffffff;struct Segmentree{ int tag[N]; #define mid ((l+r) >> 1) void Build(int x, int l, int r){ tag[x] = inf; if(l == r) return; Build(x<<1, l, mid); Build(x<<1|1, mid+1, r); } void Modify(int x, int l, int r, int L, int R, int val){ if(L<=l && r<=R){ tag[x] = min(tag[x], val); return;} if(L<=mid) Modify(x<<1, l, mid, L, R, val); if(R>mid) Modify(x<<1|1, mid+1, r, L, R, val); } int Quary(int x, int l, int r, int pos){ if(l == r) return tag[x]; if(pos <= mid) return min(Quary(x<<1, l, mid, pos), tag[x]); else return min(Quary(x<<1|1, mid+1, r, pos), tag[x]); }}Seg1, Seg2;int main(){ scanf("%s", s+1); n = strlen(s+1); tot = last = 1; for(int i=1; i<=n; i++) Extend(i, s[i] - 'a'); for(int i=1; i<=tot; i++) c[t[i].len]++; for(int i=1; i<=n; i++) c[i] += c[i-1]; for(int i=1; i<=tot; i++) A[c[t[i].len]--] = i; Seg1.Build(1, 1, n); Seg2.Build(1, 1, n); for(int i=tot; i>=1; i--){ int p = A[i]; t[t[p].link].siz += t[p].siz; if(t[p].siz > 1) continue; int Min = t[t[p].link].len + 1, Max = t[p].len, pos = t[p].pos; Seg1.Modify(1, 1, n, pos - Min + 1, pos, Min); Seg2.Modify(1, 1, n, pos - Max + 1, pos - Min + 1, pos + 1); } for(int i=1; i<=n; i++){ int v1 = Seg1.Quary(1, 1, n, i); int v2 = Seg2.Quary(1, 1, n, i) - i; printf("%d\n", min(v1, v2)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。