网站返利程序,微信公众号怎么创建优惠券,京东网站建设哪家好,知名的网站建设公司排名题意#xff1a;给一个串 SSS#xff0c;qqq 次询问#xff0c;每次给定串 TTT 和 l,rl,rl,r #xff0c;求有多少个本质不同的串是 TTT 的子串而不是 Sl…rS_{l\dots r}Sl…r 的子串。 ∣S∣≤5105,q≤105,∑∣T∣≤106|S|\leq 5\times 10^5,q\leq 10^5,\sum|T|\leq 10^…题意给一个串 SSSqqq 次询问每次给定串 TTT 和 l,rl,rl,r 求有多少个本质不同的串是 TTT 的子串而不是 Sl…rS_{l\dots r}Sl…r 的子串。
∣S∣≤5×105,q≤105,∑∣T∣≤106|S|\leq 5\times 10^5,q\leq 10^5,\sum|T|\leq 10^6∣S∣≤5×105,q≤105,∑∣T∣≤106
先考虑所有询问 l1,r∣S∣l1,r|S|l1,r∣S∣ 怎么做。
先对 SSS 建个 SAM 出来我们需要把每次询问的 TTT 放上去搞搞。如果用广义后缀自动机的话复杂度是和 SSS 有关的做不了。所以要把 TTT 就看成一个串。
考虑把 TTT 放上去匹配从 SAM 上的当前点不断跳 fail 直到有对应的转移边。这样可以得到 TTT 的每一个前缀 [1,i][1,i][1,i] 最长的 在 SSS 中出现过的 后缀长度记为 lenilen_ileni。
但我们要求的是本质不同的串还需要把上面那个东西去重。
我们一次加入 TTT 的每个字符那么当前的一个后缀合法当且仅当其长度大于 lenilen_ileni。我们可以对 TTT 再单独建一个 SAM维护每个结点 endpos 集合中的最大值然后遍历每个结点统计答案即可。
然后对于 l,rl,rl,r 任意的情况就是用可持久化线段树合并来显式维护 endpos 集合。
然后就是一通乱搞。
冷静分析一下我们要做的是当前维护的串是否在 Sl…rS_{l\dots r}Sl…r 中出现过也就是 [ls−1,r][ls-1,r][ls−1,r] 中有没有这个点的 endpos 集合中的位置其中 sss 为当前串长度。直接暴力丢掉第一个字符如果当前结点丢完了再跳父亲。转移的时候额外判一下要去的结点对应区间有没有这个点的 endpos。
因为这个串可能被砍了一半所以在更新 lenilen_ileni 的时候要在 [l,r][l,r][l,r] 里查一个 endpos 的最大值 mxmxmx和 mx−l1mx-l1mx−l1 取 min\minmin。
复杂度 O(nlogn)\Omicron(n\log n)O(nlogn)
#include iostream
#include cstring
#include cctype
#include cstdio
#define MAXN 2000005
using namespace std;
typedef long long ll;
int ch[MAXN4][2],sum[MAXN4],mxpos[MAXN4],cnt;
void modify(int x,int l,int r,int k)
{if (!x) xcnt;sum[x];if (lr) return (void)(mxpos[x]l);int mid(lr)1;if (kmid) modify(ch[x][0],l,mid,k);else modify(ch[x][1],mid1,r,k);mxpos[x]max(mxpos[ch[x][0]],mxpos[ch[x][1]]);
}
int merge(int x,int y)
{if (!x||!y) return x|y;int pcnt;ch[p][0]ch[x][0],ch[p][1]ch[x][1];ch[p][0]merge(ch[p][0],ch[y][0]);ch[p][1]merge(ch[p][1],ch[y][1]);sum[p]sum[ch[p][0]]sum[ch[p][1]];mxpos[p]max(mxpos[ch[p][0]],mxpos[ch[p][1]]);return p;
}
int query(int x,int l,int r,int ql,int qr)
{if (!x) return 0;if (qllrqr) return sum[x];if (qrl||rql) return 0;int mid(lr)1;return query(ch[x][0],l,mid,ql,qr)query(ch[x][1],mid1,r,ql,qr);
}
int querymax(int x,int l,int r,int ql,int qr)
{if (!x) return 0;if (qllrqr) return mxpos[x];if (qrl||rql) return 0;int mid(lr)1;return max(querymax(ch[x][0],l,mid,ql,qr),querymax(ch[x][1],mid1,r,ql,qr));
}
int a[MAXN],c[MAXN],pos[MAXN],n,m;
char s[MAXN],t[MAXN];
struct SAM
{int ch[MAXN][26],fa[MAXN],len[MAXN],rt[MAXN],mx[MAXN],las,tot;inline void insert(int c,int k,int type){int curtot;int plas;len[cur]len[p]1;for (;p!ch[p][c];pfa[p]) ch[p][c]cur;if (!p) fa[cur]1;else{int qch[p][c];if (len[q]len[p]1) fa[cur]q;else{int _qtot;len[_q]len[p]1;fa[_q]fa[q],fa[q]fa[cur]_q;memcpy(ch[_q],ch[q],sizeof(ch[_q]));for (;ch[p][c]q;pfa[p]) ch[p][c]_q;}}lascur;if (type) modify(rt[cur],1,n,k);else mx[cur]k;}inline void build(int type){for (int i1;itot;i) c[i]0;for (int i1;itot;i) c[len[i]];for (int i1;itot;i) c[i]c[i-1];for (int i1;itot;i) a[c[len[i]]--]i;for (int itot;i1;i--) if (fa[a[i]]) {if (type) rt[fa[a[i]]]merge(rt[fa[a[i]]],rt[a[i]]);else mx[fa[a[i]]]max(mx[fa[a[i]]],mx[a[i]]); }}inline void query(int l,int r){int cur1,s0,p0;for (int i1;im;i){while (cur1(!ch[cur][t[i]-a]||ls-1r||!::query(rt[ch[cur][t[i]-a]],1,n,lmax(s,1)-1,r)))((--s)len[fa[cur]])(curfa[cur]);(::query(rt[ch[cur][t[i]-a]],1,n,lmax(s,1)-1,r))(curch[cur][t[i]-a],s,p);pos[i]max(0,min(s,querymax(rt[cur],1,n,l,r)-l1));}}inline ll calc(){ll ans0;for (int i1;itot;i) ansmax(0,len[i]-max(len[fa[i]],pos[mx[i]]));return ans;}inline void clear(){for (int i1;itot;i) mx[i]fa[i]0,memset(ch[i],0,sizeof(ch[i]));lastot1;}inline SAM():las(1),tot(1){}
}S,T;
int main()
{scanf(%s,s1);nstrlen(s1);for (int i1;in;i) S.insert(s[i]-a,i,1);S.build(1);int q;scanf(%d,q);while (q--){scanf(%s,t1);mstrlen(t1);for (int i1;im;i) T.insert(t[i]-a,i,0);T.build(0);int l,r;scanf(%d%d,l,r);S.query(l,r);printf(%lld\n,T.calc());T.clear();}return 0;
}
