自己做的网站怎么删除,无锡今天最新通知,做网站公司的商标需要注册吗,网站建设类公司正题 题目大意
一个字符串SSS。
若干个询问#xff0c;每次询问一个串TTT和l,rl,rl,r。询问有多少个TTT和SSS的公共子串满足和为[l,r][l,r][l,r] 解题思路
考虑枚举子串左端#xff0c;那么右串一定在一个范围内#xff0c;考虑如何求出一个范围。
考虑用后缀数组解决这…正题 题目大意
一个字符串SSS。
若干个询问每次询问一个串TTT和l,rl,rl,r。询问有多少个TTT和SSS的公共子串满足和为[l,r][l,r][l,r] 解题思路
考虑枚举子串左端那么右串一定在一个范围内考虑如何求出一个范围。
考虑用后缀数组解决这个问题我们把所有串拼在一起。对与每个在TTT里的后缀我们要找到左右边的第一个SSS里的后缀然后用树状数组维护答案。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x-x)
using namespace std;
const int N6e510,lim2e6;
int n,m,q,s[N],l[N],height[N],L[N],R[N];
int x[N],y[N],sa[N],rk[N],c[N];
pairint,int p[N];
vectorint v[N],wz[N];
char st[N];
struct Tree_Array{int t[lim10];void Change(int x,int val){x;while(xlim){t[x]val;xlowbit(x);}return;}int Ask(int x){int ans0;x;if(x0)return 0;while(x){anst[x];x-lowbit(x);}return ans;}
}T;
void Init(){scanf(%s,st1);nstrlen(st1);for(int i1;in;i)s[i]st[i]-01;scanf(%d,q);for(int i1;iq;i){scanf(%s,st1);l[i]strlen(st1);s[n]11;for(int j1;jl[i];j){s[n]st[j]-01,p[n]mp(i,j);v[i].push_back(-1); wz[i].push_back(n);}scanf(%d%d,L[i],R[i]);}
}
void Qsort(){for(int i1;im;i)c[i]0;for(int i1;in;i)c[x[i]];for(int i1;im;i)c[i]c[i-1];for(int in;i1;i--)sa[c[x[y[i]]]--]y[i],y[i]0;
}
void Get_SA(){m11;for(int i1;in;i)x[i]s[i],y[i]i;Qsort();for(int w1;wn;w1){int p0;for(int in-w1;in;i)y[p]i;for(int i1;in;i)if(sa[i]w)y[p]sa[i]-w;Qsort();swap(x,y);x[sa[1]]p1;for(int i2;in;i)x[sa[i]](y[sa[i]]y[sa[i-1]]y[sa[i]w]y[sa[i-1]w])?p:p;if(pn)break;mp;}return;
}
void Get_Height(){int k0;for(int i1;in;i)rk[sa[i]]i;for(int i1;in;i){if(rk[i]1)continue;if(k)k--;int jsa[rk[i]-1];while(iknjkns[ik]s[jk])k;height[rk[i]]k;}return;
}
void Solve(){int w2147483647/3,flag0;for(int i1;in;i){int xsa[i];if(!p[x].first)w2147483647/3,flag1;else{if(flag){wmin(w,height[i]);v[p[x].first][p[x].second]w;}}}w2147483647/3;flag0;for(int in;i1;i--){int xsa[i]; if(!p[x].first)wheight[i],flag1;else{if(flag){v[p[x].first][p[x].second]max(v[p[x].first][p[x].second],w);wmin(w,height[i]);}}}return;
}
void Get_Ans(){for(int x1;xq;x){T.Change(0,1);int sum0,k0,rl[x];long long ans0;for(int il[x];i1;i--){sums[wz[x][i-1]]-1;while(rriv[x][i]){r--;T.Change(k,-1);ks[wz[x][r]]-1;}ansT.Ask(sum-L[x])-T.Ask(sum-R[x]-1);T.Change(sum,1);}while(r){r--;T.Change(k,-1);ks[wz[x][r]]-1;}T.Change(k,-1);printf(%lld\n,ans);}return;
}
int main()
{Init();Get_SA();Get_Height();Solve();Get_Ans();
}
