卡常啊
by mrsrz @ 2019-05-06 21:11:56
@[mrsrz](/space/show?uid=6813) 我尽力了..
by TopCarry @ 2019-05-06 21:14:13
感觉要$1.5s-2s$的样子，~~如果不是懒~~我其实可以学一波$O(n)$后缀排序
by TopCarry @ 2019-05-06 21:15:45
不一定是后缀排序的锅？
by mrsrz @ 2019-05-06 21:17:28
@[mrsrz](/space/show?uid=6813) 我试着注释了后面的部分，时间没差多少
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
const int N=1100000;
int x[N],y[N],tong[N],n,m,sa[N],height[N];
int S[N];
void getSA(){
register int i,k;
for(i=1;i<=n;i++)tong[x[i]=S[i]]++;
for(i=1;i<=m;i++)tong[i]+=tong[i-1];
for(i=1;i<=n;i++)sa[tong[x[i]]--]=i;
for(k=1;k<=n;k<<=1){
int cnt=0;
for(i=n-k+1;i<=n;++i)y[++cnt]=i;
for(i=1;i<=n;++i)if(sa[i]>k)y[++cnt]=sa[i]-k;
for(i=1;i<=m;++i)tong[i]=0;
for(i=1;i<=n;++i)tong[x[i]]++;
for(i=1;i<=m;++i)tong[i]+=tong[i-1];
for(i=n;i>=1;--i)sa[tong[x[y[i]]]--]=y[i];
memcpy(y,x,sizeof(y));
cnt=x[sa[1]]=1;
for(i=2;i<=n;++i)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?cnt:++cnt;
m=cnt;
if(cnt==n)break;
}
}
int val[N],lg[N],ST[N][23];
void getheight(){
register int i,j,k=0;
for(i=1;i<=n;i++)x[sa[i]]=i;
for(i=1;i<=n;i++){
if(x[i]==1)continue;
if(k)k--;
int j=sa[x[i]-1];
while(j+k<=n&&i+k<=n&&S[i+k]==S[j+k])k++;
height[x[i]]=k;
}
for(i=1;i<=n;i++)ST[i][0]=height[i];
for(j=1;j<=22;j++)
for(i=1;i+(1<<j)-1<=n;i++)
ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
int query(int x,int y){
if(x>y)swap(x,y);
int len=lg[y-x+1];
return min(ST[x][len],ST[y-(1<<len)+1][len]);
}
int suf[N];
char s[N];
queue<int> q;
void pre(){
register int i;
for(i=2;i<=n;i++)lg[i]=lg[i/2]+1;
for(i=1;i<=n;i++){
if(val[sa[i]])q.push(i);
else if(S[sa[i]]<=1){
while(!q.empty()){
int u=q.front();
suf[sa[u]]=query(u+1,i);q.pop();
}
}
}
while(!q.empty())q.pop();
for(i=n;i>=1;i--){
if(val[sa[i]])q.push(i);
else if(S[sa[i]]<=1){
while(!q.empty()){
int u=q.front();
suf[sa[u]]=max(suf[sa[u]],query(i+1,u));q.pop();
}
}
}
}
int f[N],nn,mm,tot=2,l[N],r[N],Q[N],L,R;
bool check(int Len,int u){
register int i;
for(i=0;i<=10+r[u]-l[u];i++)Q[i]=0;
for(i=l[u];i<=r[u]+1;i++)f[i]=0;
L=R=1;
for(i=r[u];i>=l[u];i--){
if(i+Len<=r[u]+1){
while(L<=R&&f[Q[R]]+Q[R]<=f[i+Len]+i+Len)R--;
Q[++R]=i+Len;
}
while(L<=R&&Q[L]>i+suf[i])L++;
f[i]=max(f[i+1],f[Q[L]]+Q[L]-i);
}
return (double)f[l[u]]>=(double)(r[u]-l[u]+1)*0.90;
}
void work(int u){
int ans=0;
int LL=1,RR=r[u]-l[u]+1;
while(LL<=RR){
int mid=(LL+RR)>>1;
if(check(mid,u))ans=mid,LL=mid+1;
else RR=mid-1;
}
cout<<ans<<'\n';
}
int main(){
register int i,j;
freopen("cheat19.in","r",stdin);
freopen("cheat.out","w",stdout);
cin>>nn>>mm;
int past=0;
for(i=1;i<=mm;i++){
scanf("%s",s+past+1);
past=strlen(s+1);
s[++past]='&';
}
for(i=1;i<=nn;i++){
scanf("%s",s+past+1);
int now=strlen(s+1);
for(j=past+1;j<=now;j++)val[j]=1;
l[i]=past+1;r[i]=now;past=now;s[++past]='&';
}
for(i=1;i<=past;i++)
if(s[i]=='&')S[i]=++tot;
else S[i]=s[i]-'0';
n=past;m=1100;
getSA();getheight();
pre();
for(i=1;i<=nn;i++){
work(i);
}
return 0;
}
/*
4 2
10110
000001110
1011001100
1011001100
1011001100
1011001100
2 1
1010101
01000100
101
1 18
101010130100010041015
*/
```
by TopCarry @ 2019-05-06 21:18:39
~~可以后缀树构造SA~~
by Hyscere @ 2019-05-06 21:37:49
# 哟呵SKR呀兄弟
by A_Soul @ 2019-05-07 16:40:07
@[TopCarry](/user/130060) 虽然但是，你读入复杂度太高了，你读入 n 篇作文的时候复杂度是 n^2 的，后面再快也没用（时隔 4 年的回复）
by __stick @ 2023-02-22 22:14:00