注册公司多少钱不用交税,南昌seo网站推广费用,免费网络软件,哪里做网站CF1037H. Security
Solution 1
设原串为ststst。
对于单个询问#xff0c;答案必然是询问串sss的一个前缀s[1..i]s[1..i]s[1..i]加上一个大于s[i1]s[i1]s[i1]的字符ccc构成。
因此我们只需要枚举前缀s[1..i]s[1..i]s[1..i]#xff0c;枚举字符ccc#xff0c;快速询问s[1…CF1037H. Security
Solution 1
设原串为ststst。
对于单个询问答案必然是询问串sss的一个前缀s[1..i]s[1..i]s[1..i]加上一个大于s[i1]s[i1]s[i1]的字符ccc构成。
因此我们只需要枚举前缀s[1..i]s[1..i]s[1..i]枚举字符ccc快速询问s[1..i]cs[1..i]cs[1..i]c有没有在st[l,r]st[l,r]st[l,r]中出现过后缀自动机线段树合并记录区间内存在的末尾位置个数即可。
时间复杂度O(26∗nlgn)O(26*nlgn)O(26∗nlgn)
Solution 2
我们发现我们用线段树合并记录区间末尾位置个数并不优我们考虑直接记录区间内是否有ccc的可行转移因为字符集只有262626我们可以把它压成2262^{26}226的intintint即可快速判断是否可以转移。
时间复杂度O((26lgn)∗n)O((26lgn)*n)O((26lgn)∗n)
Code 1
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se second
using namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN400005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char St[MAXN],st[MAXN];
int ls[MAXN*20],rs[MAXN*20],s[MAXN*20],rt[MAXN],nw[MAXN],nodenum0;
void print(int x,int y)
{for (int i1;ix;i) putchar(St[i]);putchar(ya);puts();
}int query(int x,int l,int r,int L,int R)
{if (LR||!x) return 0;if (lLrR) return s[x];int mid(lr)1;if (Rmid) return query(ls[x],l,mid,L,R);else if (Lmid) return query(rs[x],mid1,r,L,R);else return query(ls[x],l,mid,L,mid)query(rs[x],mid1,r,mid1,R);
}
int merge(int x,int y)
{if (!x||!y) return x|y;int znodenum;s[z]s[x]s[y];ls[z]merge(ls[x],ls[y]);rs[z]merge(rs[x],rs[y]);return z;
}
int update(int x,int l,int r,int y)
{if (!x) xnodenum;s[x];if (lr) return x;int mid(lr)1;if (ymid) ls[x]update(ls[x],l,mid,y);else rs[x]update(rs[x],mid1,r,y); return x;
}int t[MAXN][26],len[MAXN],fa[MAXN],Lst[MAXN],sz2,lst1;
void insert(int c,int id)
{int plst,nplstsz;len[np]len[p]1,Lst[id]np;for (;p!t[p][c];pfa[p]) t[p][c]np;if (!p) { fa[np]1; return; }int qt[p][c];if (len[q]len[p]1) fa[np]q;else{int nqsz;fa[nq]fa[q];fa[np]fa[q]nq;len[nq]len[p]1;memcpy(t[nq],t[q],sizeof t[0]);for (;t[p][c]q;pfa[p]) t[p][c]nq;}
}
int c[MAXN]{1},a[MAXN];
void Init()
{for (int i1;isz;i) c[i]0;for (int i1;isz;i) c[len[i]];for (int i1;isz;i) c[i]c[i-1];for (int isz-1;i1;i--) a[--c[len[i]]]i;for (int isz-1;i1;i--) rt[fa[a[i]]]merge(rt[fa[a[i]]],rt[a[i]]);
}
signed main()
{scanf(%s,st1);int lenstrlen(st1);for (int i1;ilen;i) insert(st[i]-a,i);for (int i1;ilen;i) rt[Lst[i]]update(rt[Lst[i]],1,sz,i);Init();int Caseread();while (Case--){int lread(),rread();scanf(%s,St1);int Lenstrlen(St1),idLen1;nw[0]1;for (int i1;iLen;i){if (t[nw[i-1]][St[i]-a]query(rt[t[nw[i-1]][St[i]-a]],1,sz,li-1,r)) nw[i]t[nw[i-1]][St[i]-a];else { idi; break; }}int flag0;for (int iid;i1;i--){for (int j(iLen?0:St[i]-a1);j26;j)if (t[nw[i-1]][j]query(rt[t[nw[i-1]][j]],1,sz,li-1,r)) { print(i-1,j),flag1; break; } if (flag) break;}if (!flag) puts(-1);}return 0;
}Code 2
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se second
using namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN400005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char St[MAXN],st[MAXN];
int ls[MAXN*20],rs[MAXN*20],s[MAXN*20],rt[MAXN],nw[MAXN],Q[MAXN],nodenum0;
void print(int x,int y)
{for (int i1;ix;i) putchar(St[i]);int t0;while (!(y1)) y1,t;putchar(ta);puts();
}int query(int x,int l,int r,int L,int R)
{if (LR||!x) return 0;if (lLrR) return s[x];int mid(lr)1;if (Rmid) return query(ls[x],l,mid,L,R);else if (Lmid) return query(rs[x],mid1,r,L,R);else return query(ls[x],l,mid,L,mid)|query(rs[x],mid1,r,mid1,R);
}
int merge(int x,int y)
{if (!x||!y) return x|y;int znodenum;s[z]s[x]|s[y];ls[z]merge(ls[x],ls[y]);rs[z]merge(rs[x],rs[y]);return z;
}
int update(int x,int l,int r,int y,int z)
{if (!x) xnodenum;s[x]|z;if (lr) return x;int mid(lr)1;if (ymid) ls[x]update(ls[x],l,mid,y,z);else rs[x]update(rs[x],mid1,r,y,z); return x;
}int t[MAXN][26],len[MAXN],fa[MAXN],Lst[MAXN],sz2,lst1;
void insert(int c,int id)
{int plst,nplstsz;len[np]len[p]1,Lst[id]np;for (;p!t[p][c];pfa[p]) t[p][c]np;if (!p) { fa[np]1; return; }int qt[p][c];if (len[q]len[p]1) fa[np]q;else{int nqsz;fa[nq]fa[q];fa[np]fa[q]nq;len[nq]len[p]1;memcpy(t[nq],t[q],sizeof t[0]);for (;t[p][c]q;pfa[p]) t[p][c]nq;}
}
int c[MAXN]{1},a[MAXN];
void Init()
{for (int i1;isz;i) c[i]0;for (int i1;isz;i) c[len[i]];for (int i1;isz;i) c[i]c[i-1];for (int isz-1;i1;i--) a[--c[len[i]]]i;for (int isz-1;i1;i--) rt[fa[a[i]]]merge(rt[fa[a[i]]],rt[a[i]]);
}
signed main()
{scanf(%s,st1);int lenstrlen(st1); Lst[0]1;for (int i1;ilen;i) insert(st[i]-a,i);for (int i1;ilen;i) rt[Lst[i-1]]update(rt[Lst[i-1]],0,sz,i-1,1(st[i]-a));Init();int Caseread();while (Case--){int lread(),rread();scanf(%s,St1);int Lenstrlen(St1),idLen;nw[0]1;for (int i1;iLen;i){if (((Q[i-1]query(rt[nw[i-1]],0,sz,li-2,r-1))(St[i]-a))1) nw[i]t[nw[i-1]][St[i]-a];else { idi-1; break; }}Q[Len]query(rt[nw[Len]],0,sz,lLen-1,r-1);int flag0;for (int iid;i0;i--){int pQ[i],q(iLen?0:St[i1]-a1);if (p(1q)) { p^p((1q)-1),print(i,p(-p)),flag1; break; }}if (!flag) puts(-1);}return 0;
}
