做网站的广告语,成都网站快速开发,中国企业集成网网址,软文标题大全解析
算是一个比较高级的SAM的应用了 对fail树的dfs序建立维护右端点最大值的线段树 考虑把所有的询问离线#xff0c;按照右端点排序 每次动态把当前询问右端点左侧的前缀插入线段树 处理询问时#xff0c;先贪心的尝试和询问串填法一样#xff0c;如果不行就往下一个字母…解析
算是一个比较高级的SAM的应用了 对fail树的dfs序建立维护右端点最大值的线段树 考虑把所有的询问离线按照右端点排序 每次动态把当前询问右端点左侧的前缀插入线段树 处理询问时先贪心的尝试和询问串填法一样如果不行就往下一个字母填 判断合法的标志就是左端点的最大值是否不小于询问的左端点
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e5100;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
int n,m;
struct node{int len,fa;int tr[26];
}st[N];
int tot(1),lst(1),id[N];
void ins(int c,int ide){c-a;int curtot,plst;lsttot;st[cur].lenst[p].len1;id[ide]cur;for(;p!st[p].tr[c];pst[p].fa) st[p].tr[c]cur;if(!st[p].tr[c]) st[cur].fa1;else{int qst[p].tr[c];if(st[q].lenst[p].len1) st[cur].faq;else{int pptot;st[pp]st[q];st[pp].lenst[p].len1;st[q].fast[cur].fapp;for(;pst[p].tr[c]q;pst[p].fa) st[p].tr[c]pp;return;}}
}struct
#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
segment_tree{int mx[N2];int ask(int k,int l,int r,int x,int y){if(xlry) return mx[k];int res0;if(xmid) resmax(res,ask(ls,l,mid,x,y));if(ymid) resmax(res,ask(rs,mid1,r,x,y)); //if(k1) printf(---ask: (%d %d) res%d\n,x,y,res);return res;}void upd(int k,int l,int r,int p,int w){//if(k1) printf(---upd: p%d w%d\n,p,w);if(lr){mx[k]max(mx[k],w);return;}if(pmid) upd(ls,l,mid,p,w);else upd(rs,mid1,r,p,w);mx[k]max(mx[ls],mx[rs]);return;}
}t;string s,ss,ask[N],ans[N];
struct query{int id,l,r,len;bool operator (const query o)const{return ro.r;}
}q[N];
int St[N],tim,Ed[N];
vectorintv[N];
void dfs(int x){St[x]tim;for(const auto to:v[x]) dfs(to);Ed[x]tim;return;
}
bool jd[N];
inline bool check(int x,int l,int len){//printf( check:x%d l%d len%d ask%d\n,x,l,len,t.ask(1,1,tim,St[x],Ed[x]));return t.ask(1,1,tim,St[x],Ed[x])-len1l;
}
bool find(int x,int len,int o,int idx){if(lenq[idx].len){for(int i0;i25;i){if(st[x].tr[i]check(st[x].tr[i],q[idx].l,len)){jd[o]1;ans[o]ai;//printf(ok x%d to%d\n,x,st[x].tr[i]);return true;}}return false;} int cask[o][len]-a;//printf(x%d len%d c%d\n,x,len,c);if(st[x].tr[c]check(st[x].tr[c],q[idx].l,len)find(st[x].tr[c],len1,o,idx)){ans[o]ac;return true;}else{for(int ic1;i25;i){ if(st[x].tr[i]check(st[x].tr[i],q[idx].l,len)){//printf(?? o%d ask%d len%d\n,o,t.ask(1,1,tim,St[st[x].tr[i]],Ed[st[x].tr[i]]),len);jd[o]1;ans[o]ai;return true;}}return false;}
}
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifcins;s.insert(s.begin(), );ns.size()-1;for(int i1;in;i) ins(s[i],i);for(int i2;itot;i) v[st[i].fa].push_back(i);dfs(1);//for(int i1;itot;i) printf(i%d fa%d (%d %d)\n,i,st[i].fa,St[i],Ed[i]);mread();for(int i1;im;i){q[i].lread();q[i].rread();q[i].idi;cinask[i];ask[i].insert(ask[i].begin(), );//if(i75){//printf((%d %d) ,q[i].l,q[i].r);coutask[i]endl;//}q[i].lenask[i].size()-1;}sort(q1,q1m);int pl0;for(int i1;im;i){while(plq[i].r){pl;t.upd(1,1,tim,St[id[pl]],pl);//printf(upd: node%d pos%d\n,id[pl],St[id[pl]]);}find(1,1,q[i].id,i);}for(int i1;im;i){if(!jd[i]) printf(-1\n);else{for(int jans[i].size()-1;j0;j--) putchar(ans[i][j]);putchar(\n);}}return 0;
}
/*
*/
