百度飙风算法 小网站,军事新闻app哪个好,wordpress怎么才能快,wordpress slide插件正题
题目链接:https://www.luogu.com.cn/problem/P4770 题目大意
给出一个长度为nnn的字符串SSS。qqq次询问给出一个串TTT和一个区间[L,R][L,R][L,R]#xff0c;求TTT有多少个本质不同的子串不是SL∼RS_{L\sim R}SL∼R的子串。 1≤n≤5105,1≤Q≤105,∑∣T∣≤1061\leq n…正题
题目链接:https://www.luogu.com.cn/problem/P4770 题目大意
给出一个长度为nnn的字符串SSS。qqq次询问给出一个串TTT和一个区间[L,R][L,R][L,R]求TTT有多少个本质不同的子串不是SL∼RS_{L\sim R}SL∼R的子串。
1≤n≤5×105,1≤Q≤105,∑∣T∣≤1061\leq n\leq 5\times 10^5,1\leq Q\le 10^5,\sum|T|\leq 10^61≤n≤5×105,1≤Q≤105,∑∣T∣≤106 解题思路
因为给了很多L1,RnL1,RnL1,Rn的部分分所以应该是提示我们先从这个方面考虑。 这个部分比较简单考虑改为求有多少个本质不同的子串在SL∼RS_{L\sim R}SL∼R中出现过因为是本质不同的子串我们可以先建一个SSS的SAMSAMSAM和一个TTT的SAMSAMSAM。
然后把TTT串拿到SSS的SAMSAMSAM上面跑然后每次跑出来的一个匹配长度记为lenlenlen。对于TTT的SAMSAMSAM上的每一个节点我们记录一个pospospos表示这个节点属于的长度位置然后跑到这个位置的lenlenlen就是能够匹配的长度了记为ansansans。然后答案就是max{leni−max{ansposi,lenfai},0}max\{len_i-max\{ans_{pos_i},len_{fa_i}\},0\}max{leni−max{ansposi,lenfai},0}防匹配长度超出[lenfai,leni][len_{fa_i},len_i][lenfai,leni]的范围
这样一次的时间复杂度就是O(∣T∣)O(|T|)O(∣T∣)的了。
然后考虑带区间的怎么做我们需要保证我们在SSS的SAMSAMSAM上面跳的时候需要保证这些节点都是属于SL∼RS_{L\sim R}SL∼R的自动机上的而且要保证我们提取出来的lenlenlen也是在那个上面的。
其实如果这个节点的endposendposendpos类里面有L∼RL\sim RL∼R的信息就好了这个用线段树合并维护一下endposendposendpos类的信息就可以了。
时间复杂度O((n∑∣T∣)logn)O((n\sum |T|)\log n)O((n∑∣T∣)logn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const int N1e610;
int n,q,ql,qr,p[N],c[N],rt[N],ans[N],pos[N];
char s[N];
struct SegTree{int cnt,w[N5],ls[N5],rs[N5];int Change(int x,int L,int R,int pos){int pcnt;w[p]max(w[x],pos);if(LR)return p;int mid(LR)1;if(posmid)ls[p]Change(ls[x],L,mid,pos),rs[p]rs[x];else rs[p]Change(rs[x],mid1,R,pos),ls[p]ls[x];return p;}int Ask(int x,int L,int R,int l,int r){if(!x)return 0;if(LlRr)return w[x];int mid(LR)1;if(rmid)return Ask(ls[x],L,mid,l,r);if(lmid)return Ask(rs[x],mid1,R,l,r);return max(Ask(ls[x],L,mid,l,mid),Ask(rs[x],mid1,R,mid1,r));}int Merge(int x,int y){if(!x||!y)return xy;int pcnt;w[p]max(w[x],w[y]);ls[p]Merge(ls[x],ls[y]);rs[p]Merge(rs[x],rs[y]);return p;}
}R;
struct SAM{int cnt,last,ch[N][26],len[N],fa[N];void init(){memset(ch[1],0,sizeof(ch[1]));lastcnt1;}int Insert(int c){int plast,nplastcnt;len[np]len[p]1;memset(ch[np],0,sizeof(ch[np]));for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{int qch[p][c];if(len[p]1len[q])fa[np]q;else{int nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]fa[np]nq;pos[nq]pos[q];for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}lastnp;return np;}void Build(){for(int i1;icnt;i)c[len[i]];for(int i1;in;i)c[i]c[i-1];for(int i1;icnt;i)p[c[len[i]]--]i;for(int icnt;i1;i--){int xp[i];rt[fa[x]]R.Merge(rt[fa[x]],rt[x]);}return;}void next(int x,int l,int c){while(x){if(ch[x][c]){int maxlR.Ask(rt[ch[x][c]],1,n,1,qr)-ql1;if(len[fa[x]]maxl){lmin(l1,maxl);xch[x][c];return;}}xfa[x];llen[x];}l0;x1;return;}ll calc(){ll prt0;for(int i2;icnt;i)prtmax(len[i]-max(ans[pos[i]],len[fa[i]]),0);return prt;}
}S,T;
void work(char *s){int mstrlen(s1);T.init();for(int i1;im;i){int xT.Insert(s[i]-a);pos[x]i;}int x1,l0;for(int i1;im;i){int cs[i]-a;S.next(x,l,c);ans[i]l;}printf(%lld\n,T.calc());
}
signed main()
{scanf(%s,s1);nstrlen(s1);S.init();for(int i1;in;i){int xS.Insert(s[i]-a);rt[x]R.Change(rt[x],1,n,i);}S.Build();scanf(%d,q);while(q--){scanf(%s,s1);scanf(%d%d,ql,qr);work(s);}return 0;
}
