題面
BZOJ
洛谷
題解
很有趣的一道題啊
對于在所有的串上面進行比對?
很明顯的字尾自動機
是以先建構出廣義字尾自動機
然後這個拆分很像一個 dp
同時,要求的東西很像一個可以二分的樣子
是以二分一個答案,考慮如何 dp
設 f[i] 表示處理完前 i 個字元,能夠比對上的最多的字元個數
轉移是f[i]=max(f[j]+i−j),滿足 i−j>mid
同時 S[j+1..i] 能夠比對上
是以,可以提前預處理出每個位置能夠比對上的最大長度
然後利用單調隊列進行轉移就行啦
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 1111111
inline int read()
{
RG int x=,t=;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-,ch=getchar();
while(ch<='9'&&ch>='0')x=x*+ch-,ch=getchar();
return x*t;
}
struct Node
{
int son[];
int ff,len;
}t[MAX];
char ch[MAX];
int p[MAX],f[MAX];
int last=,tot=;
int Q[MAX],H,T;
int n,m;
void extend(int c)
{
int p=last,np=++tot;last=np;
t[np].len=t[p].len+;
while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;
if(!p)t[np].ff=;
else
{
int q=t[p].son[c];
if(t[q].len==t[p].len+)t[np].ff=q;
else
{
int nq=++tot;
t[nq]=t[q];
t[nq].len=t[p].len+;
t[q].ff=t[np].ff=nq;
while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
}
}
}
void pre()
{
int len=strlen(ch+);
int now=,ml=;
for(int i=;i<=len;++i)
{
int c=ch[i]-;
if(t[now].son[c])now=t[now].son[c],ml+=;
else
{
while(now&&!t[now].son[c])now=t[now].ff;
if(!now)ml=,now=;
else ml=t[now].len+,now=t[now].son[c];
}
p[i]=ml;
}
}
bool check(int k)
{
int l=strlen(ch+);
H=;T=;
for(int i=;i<=l;++i)
{
f[i]=f[i-];
if(i<k)continue;
while(H<=T&&f[Q[T]]-Q[T]<=f[i-k]-i+k)--T;
Q[++T]=i-k;
while(H<=T&&Q[H]<i-p[i])++H;
if(H<=T)f[i]=max(f[i],f[Q[H]]+i-Q[H]);
}
return f[l]*>=l*;
}
int main()
{
n=read();m=read();
while(m--)
{
last=;
scanf("%s",ch+);
for(int i=,l=strlen(ch+);i<=l;++i)extend(ch[i]-);
}
while(n--)
{
scanf("%s",ch+);
int len=strlen(ch+);
pre();
int l=,r=len,ans=;
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid))ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
return ;
}