【LOJ】#2720. 「NOI2018」你的名字

Myth丶恋晨 2021-11-01 13:48 332阅读 0赞

### 题解 ###

把S串建一个后缀自动机

用一个可持久化权值线段树维护每个节点的right集合是哪些节点

求本质不同的子串我们就是要求T串中以每个点为结束点的串有多少在\\(S\[l..r\]\\)中出现过

首先我们需要对于T串每个点本身和自己的匹配长度，可以建一个后缀自动机来完成

然后把T串放在S串上跑匹配，匹配到下一个点x时，匹配的长度是len，如果x所在的right集合在\\(\[l + len - 1,r\]\\)中没有，那么就不合法，把长度减少，如果长度减少到和父亲节点的长度一样，则需要把当前节点跳到父亲节点上

### 代码 ###

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <random> #include <ctime> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define MAXN 1000005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) { res = 0;T f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } template<class T> void out(T x) { if(x < 0) {x = -x;putchar('-');} if(x >= 10) out(x / 10); putchar('0' + x % 10); } char s[MAXN],t[MAXN]; int N,Q,val[MAXN]; int64 ans[MAXN]; struct tr_node { int lc,rc; }tr[MAXN * 40]; int Ncnt,rt[MAXN * 2]; int Find(int u,int l,int r,int ql,int qr) { if(!u) return -1; if(l > qr || r < ql) return -1; if(l == r) return l; int mid = (l + r) >> 1; int res = Find(tr[u].rc,mid + 1,r,ql,qr); if(res == -1) res = Find(tr[u].lc,l,mid,ql,qr); return res; } void Insert(int &u,int v,int l,int r,int p) { u = ++Ncnt; tr[u] = tr[v]; if(l == r) return; int mid = (l + r) >> 1; if(p <= mid) Insert(tr[u].lc,tr[v].lc,l,mid,p); else Insert(tr[u].rc,tr[v].rc,mid + 1,r,p); } int Merge(int u,int v) { if(!u || !v) return u + v; int res = ++Ncnt; tr[res].lc = Merge(tr[u].lc,tr[v].lc); tr[res].rc = Merge(tr[u].rc,tr[v].rc); return res; } int que[MAXN * 2],c[MAXN]; struct sam { struct node { int par,len,nxt[26],cnt; }tr[MAXN * 2]; int tail,root,last; void Init() { tail = 0; root = last = ++tail; memset(tr[tail].nxt,0,sizeof(tr[tail].nxt)); tr[tail].par = tr[tail].len = 0; } void build(int c) { int nw = ++tail,p; memset(tr[nw].nxt,0,sizeof(tr[nw].nxt)); tr[nw].len = tr[last].len + 1;tr[nw].cnt = 1; for(p = last ; p && !tr[p].nxt[c] ; p = tr[p].par) { tr[p].nxt[c] = nw; } if(!p) tr[nw].par = root; else { int q = tr[p].nxt[c]; if(tr[q].len == tr[p].len + 1) tr[nw].par = q; else { int cq = ++tail; tr[cq] = tr[q];tr[cq].cnt = 0; tr[cq].len = tr[p].len + 1; tr[nw].par = tr[q].par = cq; for(;p && tr[p].nxt[c] == q ; p = tr[p].par) { tr[p].nxt[c] = cq; } } } last = nw; } void calc() { for(int i = 1 ; i <= tail ; ++i) c[tr[i].len]++; for(int i = 1 ; i <= N ; ++i) c[i] += c[i - 1]; for(int i = 1 ; i <= tail ; ++i) { que[c[tr[i].len]--] = i; } for(int i = tail ; i >= 1 ; --i) { int u = que[i]; if(tr[u].cnt) Insert(rt[u],rt[u],1,N,tr[u].len); int f = tr[u].par; rt[f] = Merge(rt[f],rt[u]); } } }sam[2]; bool check(int p,int l,int r,int c) { int t = Find(rt[p],1,N,l,r); if(t == -1) return false; return (t - l + 1) >= c; } void Solve() { scanf("%s",s + 1); N = strlen(s + 1); read(Q); sam[0].Init(); for(int i = 1 ; i <= N ; ++i) { sam[0].build(s[i] - 'a'); } sam[0].calc(); int l,r,len; for(int i = 1 ; i <= Q ; ++i) { scanf("%s",t + 1); read(l);read(r); len = strlen(t + 1); sam[1].Init(); for(int j = 1 ; j <= len ; ++j) { sam[1].build(t[j] - 'a'); int f = sam[1].tr[sam[1].last].par; val[j] = sam[1].tr[f].len; } int p = sam[0].root,c = 0; for(int j = 1 ; j <= len ; ++j) { int h = t[j] - 'a'; while(p && !sam[0].tr[p].nxt[h]) { p = sam[0].tr[p].par; c = sam[0].tr[p].len; } if(!sam[0].tr[p].nxt[h]) { c = 0;p = sam[0].root; } else { p = sam[0].tr[p].nxt[h];++c; while(!check(p,l,r,c)) { --c; int f = sam[0].tr[p].par; if(c == sam[0].tr[f].len) p = f; } } val[j] = max(val[j],c); ans[i] += j - val[j]; } } for(int i = 1 ; i <= Q ; ++i) { out(ans[i]);enter; } } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #else freopen("name.in","r",stdin); freopen("name.out","w",stdout); #endif Solve(); return 0; }

转载于:https://www.cnblogs.com/ivorysi/p/11166258.html