已备案网站注册,中卫平面设计招聘,做母婴的网站有哪些,网站建设报告 商业价值正题
题目链接:https://www.luogu.com.cn/problem/P4022 题目大意
给出mmm个模板串。
然后nnn次询问给出一个串SSS要求找到一个最大的LLL使得能够将SSS超过90%90\%90%的部分拿出来分后每个串都是某个模板串的子串且长度不小于LLL。
所有输入文件长度不超过 110000011000001…正题
题目链接:https://www.luogu.com.cn/problem/P4022 题目大意
给出mmm个模板串。
然后nnn次询问给出一个串SSS要求找到一个最大的LLL使得能够将SSS超过90%90\%90%的部分拿出来分后每个串都是某个模板串的子串且长度不小于LLL。
所有输入文件长度不超过 110000011000001100000 字节。字符集为{0,1}\{0,1\}{0,1} 解题思路
先把模板串拿出来构一个广义SAM然后考虑用这个对串进行匹配。
先对于每个位置求出一个lenilen_ileni表示一个最长的长度使得iii的后缀是某个模板串的子串。
然后考虑二分一个LLL后进行dpdpdp。
那么有 fimax{fi−1,fji−j}(j∈[i−leni,i−L))f_imax\{f_{i-1},f_ji-j\}(\ j\in[i-len_i,i-L)\ )fimax{fi−1,fji−j}( j∈[i−leni,i−L) )
因为i−lenii-len_ii−leni单调所以把jjj丢进单调队列里就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1200000;
int n,m,cnt,f[N],q[N],ml[N];
int ch[N][2],len[N],fa[N];
char s[N];
int Insert(int p,int c){if(ch[p][c]){int qch[p][c];if(len[p]1len[q])return q;else{int nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;return nq; }}int npcnt;len[np]len[p]1;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;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return np;
}
bool check(int L,int n){int head1,tail0,ans0;for(int i1;in;i){if(iL){int ji-L;while(headtailf[j]-jf[q[tail]]-q[tail])tail--;q[tail]j;}while(headtailq[head]i-ml[i])head;f[i]0;if(headtail)f[i]f[q[head]]i-q[head];f[i]max(f[i],f[i-1]);ansmax(ans,f[i]);}return (ans*10n*9);
}
int main()
{scanf(%d%d,n,m);cnt1;for(int i1;im;i){scanf(%s,s1);int lstrlen(s1),x1;for(int j1;jl;j)xInsert(x,s[j]-0);}while(n--){scanf(%s,s1);int slstrlen(s1),x1,L0;for(int i1;isl;i){int cs[i]-0;while(x!ch[x][c]){xfa[x];Llen[x];}if(x)xch[x][c],L;else x1,L0;ml[i]L;}int l1,rsl;while(lr){int mid(lr)1;if(check(mid,sl))lmid1;else rmid-1;}printf(%d\n,r);}return 0;
}
